## 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 - DOI: https://doi.org/10.1090/S0894-0347-1988-0928904-4
- PDF | Request permission

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

## References

- H. S. M. Coxeter,
*Non-Euclidean Geometry*, Mathematical Expositions, No. 2, University of Toronto Press, Toronto, Ont., 1942. MR**0006835** - Karel Culik II and Derick Wood,
*A note on some tree similarity measures*, Inform. Process. Lett.**15**(1982), no. 1, 39–42. MR**678031**, DOI 10.1016/0020-0190(82)90083-7 - A. K. Dewdney,
*Wagner’s theorem for torus graphs*, Discrete Math.**4**(1973), 139–149. MR**309773**, DOI 10.1016/0012-365X(73)90076-9 - Martin Gardner,
*Time travel and other mathematical bewilderments*, W. H. Freeman and Company, New York, 1988. MR**905872** - Donald E. Knuth,
*The art of computer programming. Volume 3*, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR**0445948** - John Milnor,
*Hyperbolic geometry: the first 150 years*, Bull. Amer. Math. Soc. (N.S.)**6**(1982), no. 1, 9–24. MR**634431**, DOI 10.1090/S0273-0979-1982-14958-8 - Jean Pallo,
*On the rotation distance in the lattice of binary trees*, Inform. Process. Lett.**25**(1987), no. 6, 369–373. MR**905781**, DOI 10.1016/0020-0190(87)90214-6 - Daniel Dominic Sleator and Robert Endre Tarjan,
*Self-adjusting binary search trees*, J. Assoc. Comput. Mach.**32**(1985), no. 3, 652–686. MR**796206**, DOI 10.1145/3828.3835 - B. Ya. Ryabko, R. Nigel Horspool, and Gordon V. Cormack,
*Comments to: “A locally adaptive data compression scheme” [Comm. ACM 29 (1986), no. 4, 320–330; MR0835044 (87e:68020)] by J. L. Bentley, D. D. Sleator, R. E. Tarjan and V. K. Wei*, Comm. ACM**30**(1987), no. 9, 792–794. MR**904133**, DOI 10.1145/30401.315747 - Robert Endre Tarjan,
*Data structures and network algorithms*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1983. MR**826534**, DOI 10.1137/1.9781611970265
W. P. Thurston and J. R. Weeks, - W. T. Tutte,
*A theorem on planar graphs*, Trans. Amer. Math. Soc.**82**(1956), 99–116. MR**81471**, DOI 10.1090/S0002-9947-1956-0081471-8
K. Wagner, - Hassler Whitney,
*A theorem on graphs*, Ann. of Math. (2)**32**(1931), no. 2, 378–390. MR**1503003**, DOI 10.2307/1968197

*The mathematics of three-dimensional manifolds*, Scientific American

**251**(1984), 108-120. W. P. Thurston,

*The geometry and topology of three-dimensional manifolds*, Princeton Univ., Dept. of Math., 1979.

*Bemerkungen zum Vierfarbenproblem*, J. Deutschen Math.-Verein.

**46**(1936), 26-32.

## 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: https://doi.org/10.1090/S0894-0347-1988-0928904-4
- MathSciNet review: 928904