Rotation distance, triangulations, and hyperbolic geometry

Abstract

A <italic>rotation</italic> 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 <italic>rotation distance</italic> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 n minus 6"> <mml:semantics> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:mo>−</mml:mo> <mml:mn>6</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">2n - 6</mml:annotation> </mml:semantics> </mml:math> </inline-formula> on the maximum rotation distance between two <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-node trees for all large <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The hard and novel part of the proof is the lower bound, which makes use of volumetric arguments in hyperbolic <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="3"> <mml:semantics> <mml:mn>3</mml:mn> <mml:annotation encoding="application/x-tex">3</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-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.