Rotation distance, triangulations, and hyperbolic geometry

Daniel D. Sleator, Robert E. Tarjan, William P. Thurston

Research output: Contribution to journalArticlepeer-review

213 Scopus citations

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. 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.

Original languageEnglish (US)
Pages (from-to)647-681
Number of pages35
JournalJournal of the American Mathematical Society
Volume1
Issue number3
DOIs
StatePublished - Jul 1988

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Rotation distance, triangulations, and hyperbolic geometry'. Together they form a unique fingerprint.

Cite this