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

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

MathSciNet review:
928904

Full-text PDF

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. M. S. Coxeter,*Non-Euclidean geometry*, Univ. Toronto Press, Toronto, 1942. MR**0006835 (4:50a)****[2]**K. Culik and D. Wood,*A note on some tree similarity measures*, Inform. Process. Lett.**15**(1982), 39-42. MR**678031 (83k:68059)****[3]**A. K. Dewdney,*Wagner's theorem for torus graphs*, Discrete Math.**4**(1973), 139-149. MR**0309773 (46:8878)****[4]**M. Gardner,*Time travel and other mathematical bewilderments*, Freeman, New York, NY, 1987. MR**905872 (89b:00005)****[5]**D. E. Knuth,*The art of computer programming, Vol. 3: Sorting and searching*, Addison-Wesley, Reading, MA, 1973. MR**0445948 (56:4281)****[6]**J. Milnor,*Hyperbolic geometry: the first 150 years*, Bull. Amer. Math. Soc.**6**(1982), 9-24. MR**634431 (82m:57005)****[7]**J. Pallo,*On rotation distance in the lattice of binary trees*, Inform. Process. Lett.**25**(1987), 369-373. MR**905781****[8]**D. D. Sleator and R. E. Tarjan,*Self-adjusting binary search trees*, J. Assoc. Comput. Mach.**32**(1985), 652-686. MR**796206 (87a:68032)****[9]**D. D. Sleator, R. E. Tarjan, and W. P. Thurston,*Rotation distance, triangulations, and hyperbolic geometry*, Proc. 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, CA, Association for Computing Machinery, NY, pp. 122-135. MR**904133 (89a:68045)****[10]**R. E. Tarjan,*Data structures and network algorithms*, Soc. Indust. Appl. Math., Philadelphia, PA, 1983. MR**826534 (87g:68029)****[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 (18:408e)****[14]**K. Wagner,*Bemerkungen zum Vierfarbenproblem*, J. Deutschen Math.-Verein.**46**(1936), 26-32.**[15]**H. Whitney,*A theorem on graphs*, Ann. of Math.**32**(1931), 378-390. MR**1503003**

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

Article copyright:
© Copyright 1988
American Mathematical Society