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

VL - 1

SP - 647

EP - 681

JO - Journal of the American Mathematical Society

JF - Journal of the American Mathematical Society

SN - 0894-0347

IS - 3

ER -