TY - JOUR
T1 - Rotation distance, triangulations, and hyperbolic geometry
AU - Sleator, Daniel D.
AU - Tarjan, Robert E.
AU - Thurston, William P.
PY - 1988/7
Y1 - 1988/7
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84968502341&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84968502341&partnerID=8YFLogxK
U2 - 10.1090/S0894-0347-1988-0928904-4
DO - 10.1090/S0894-0347-1988-0928904-4
M3 - Article
AN - SCOPUS:84968502341
SN - 0894-0347
VL - 1
SP - 647
EP - 681
JO - Journal of the American Mathematical Society
JF - Journal of the American Mathematical Society
IS - 3
ER -