Rotation distance, triangulations, and hyperbolic geometry

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.