Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

Rotation distance, triangulations, and hyperbolic geometry


Authors: Daniel D. Sleator, Robert E. Tarjan and William P. Thurston
Journal: J. Amer. Math. Soc. 1 (1988), 647-681
MSC: Primary 68P05; Secondary 05C05, 05C35, 51M10, 68R10
MathSciNet review: 928904
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A rotation in a binary tree is a local restructuring that changes the tree into another tree. Rotations are useful in the design of tree-based data structures. The rotation distance between a pair of trees is the minimum number of rotations needed to convert one tree into the other. In this paper we establish a tight bound of $ 2n - 6$ on the maximum rotation distance between two $ n$-node trees for all large $ n$. The hard and novel part of the proof is the lower bound, which makes use of volumetric arguments in hyperbolic $ 3$-space. Our proof also gives a tight bound on the minimum number of tetrahedra needed to dissect a polyhedron in the worst case and reveals connections among binary trees, triangulations, polyhedra, and hyperbolic geometry.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 68P05, 05C05, 05C35, 51M10, 68R10

Retrieve articles in all journals with MSC: 68P05, 05C05, 05C35, 51M10, 68R10


Additional Information

DOI: http://dx.doi.org/10.1090/S0894-0347-1988-0928904-4
PII: S 0894-0347(1988)0928904-4
Article copyright: © Copyright 1988 American Mathematical Society