Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

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

 
 

 

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 $ 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 [Enhancements On Off] (What's this?)

  • [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

Similar Articles

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

American Mathematical Society