Rotation distance, triangulations, and hyperbolic geometry
HTML articles powered by AMS MathViewer
- by Daniel D. Sleator, Robert E. Tarjan and William P. Thurston PDF
- J. Amer. Math. Soc. 1 (1988), 647-681 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.
- 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, 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.
- 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, Bemerkungen zum Vierfarbenproblem, J. Deutschen Math.-Verein. 46 (1936), 26-32.
- Hassler Whitney, A theorem on graphs, Ann. of Math. (2) 32 (1931), no. 2, 378–390. MR 1503003, DOI 10.2307/1968197
- © 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