Rotation distance, triangulations, and hyperbolic geometry

Authors:
Daniel D. Sleator, Robert E. Tarjan and William P. Thurston

Journal:
J. Amer. Math. Soc. **1** (1988), 647-681

MSC:
Primary 68P05; Secondary 05C05, 05C35, 51M10, 68R10

MathSciNet review:
928904

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 on the maximum rotation distance between two -node trees for all large . The hard and novel part of the proof is the lower bound, which makes use of volumetric arguments in hyperbolic -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.

**[1]**H. S. M. Coxeter,*Non-Euclidean Geometry*, Mathematical Expositions, no. 2, University of Toronto Press, Toronto, Ont., 1942. MR**0006835****[2]**Karel Culik II and Derick Wood,*A note on some tree similarity measures*, Inform. Process. Lett.**15**(1982), no. 1, 39–42. MR**678031**, 10.1016/0020-0190(82)90083-7**[3]**A. K. Dewdney,*Wagner’s theorem for torus graphs*, Discrete Math.**4**(1973), 139–149. MR**0309773****[4]**Martin Gardner,*Time travel and other mathematical bewilderments*, W. H. Freeman and Company, New York, 1988. MR**905872****[5]**Donald E. Knuth,*The art of computer programming. Volume 3*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching; Addison-Wesley Series in Computer Science and Information Processing. MR**0445948****[6]**John Milnor,*Hyperbolic geometry: the first 150 years*, Bull. Amer. Math. Soc. (N.S.)**6**(1982), no. 1, 9–24. MR**634431**, 10.1090/S0273-0979-1982-14958-8**[7]**Jean Pallo,*On the rotation distance in the lattice of binary trees*, Inform. Process. Lett.**25**(1987), no. 6, 369–373. MR**905781**, 10.1016/0020-0190(87)90214-6**[8]**Daniel Dominic Sleator and Robert Endre Tarjan,*Self-adjusting binary search trees*, J. Assoc. Comput. Mach.**32**(1985), no. 3, 652–686. MR**796206**, 10.1145/3828.3835**[9]**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**, 10.1145/30401.315747**[10]**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****[11]**W. P. Thurston and J. R. Weeks,*The mathematics of three-dimensional manifolds*, Scientific American**251**(1984), 108-120.**[12]**W. P. Thurston,*The geometry and topology of three-dimensional manifolds*, Princeton Univ., Dept. of Math., 1979.**[13]**W. T. Tutte,*A theorem on planar graphs*, Trans. Amer. Math. Soc.**82**(1956), 99–116. MR**0081471**, 10.1090/S0002-9947-1956-0081471-8**[14]**K. Wagner,*Bemerkungen zum Vierfarbenproblem*, J. Deutschen Math.-Verein.**46**(1936), 26-32.**[15]**Hassler Whitney,*A theorem on graphs*, Ann. of Math. (2)**32**(1931), no. 2, 378–390. MR**1503003**, 10.2307/1968197

Retrieve articles in *Journal of the American Mathematical Society*
with MSC:
68P05,
05C05,
05C35,
51M10,
68R10

Retrieve articles in all journals with MSC: 68P05, 05C05, 05C35, 51M10, 68R10

Additional Information

DOI:
http://dx.doi.org/10.1090/S0894-0347-1988-0928904-4

Article copyright:
© Copyright 1988
American Mathematical Society