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

Article copyright: © Copyright 1988 American Mathematical Society