Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-131-88
Rotation Distance, Triangulations and Hyperbolic Geometry
Authors: Sleator, Daniel, Tarjan, Robert E., Thurston, William P.
Date:January 1988
Pages:38
Download Formats: [PDF]
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, using 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.