Rotation distance, triangulations, and hyperbolic geometry

Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P.

doi:10.1090/S0894-0347-1988-0928904-4

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

The mathematics of three-dimensional manifolds

251

The geometry and topology of three-dimensional manifolds

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

Bemerkungen zum Vierfarbenproblem

46

Hassler Whitney, A theorem on graphs, Ann. of Math. (2) 32 (1931), no. 2, 378–390. MR 1503003, DOI 10.2307/1968197