Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.83.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Rotation distance, triangulations, and hyperbolic geometry
HTML articles powered by AMS MathViewer

by Daniel D. Sleator, Robert E. Tarjan and William P. Thurston
J. Amer. Math. Soc. 1 (1988), 647-681


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.
Similar Articles
Bibliographic Information
  • © Copyright 1988 American Mathematical Society
  • Journal: J. Amer. Math. Soc. 1 (1988), 647-681
  • MSC: Primary 68P05; Secondary 05C05, 05C35, 51M10, 68R10
  • DOI:
  • MathSciNet review: 928904