Rotation distance, triangulations, and hyperbolic geometry
Authors:
Daniel D. Sleator, Robert E. Tarjan and William P. Thurston
Journal:
J. Amer. Math. Soc. 1 (1988), 647681
MSC:
Primary 68P05; Secondary 05C05, 05C35, 51M10, 68R10
MathSciNet review:
928904
Fulltext 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 treebased 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, NonEuclidean Geometry, Mathematical
Expositions, no. 2, University of Toronto Press, Toronto, Ont., 1942. MR 0006835
(4,50a)
 [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
(83k:68059), http://dx.doi.org/10.1016/00200190(82)900837
 [3]
A.
K. Dewdney, Wagner’s theorem for torus graphs, Discrete
Math. 4 (1973), 139–149. MR 0309773
(46 #8878)
 [4]
Martin
Gardner, Time travel and other mathematical bewilderments, W.
H. Freeman and Company, New York, 1988. MR 905872
(89b:00005)
 [5]
Donald
E. Knuth, The art of computer programming. Volume 3,
AddisonWesley Publishing Co., Reading, Mass.LondonDon Mills, Ont., 1973.
Sorting and searching; AddisonWesley Series in Computer Science and
Information Processing. MR 0445948
(56 #4281)
 [6]
John
Milnor, Hyperbolic geometry: the first 150
years, Bull. Amer. Math. Soc. (N.S.)
6 (1982), no. 1,
9–24. MR
634431 (82m:57005), http://dx.doi.org/10.1090/S027309791982149588
 [7]
Jean
Pallo, On the rotation distance in the lattice of binary
trees, Inform. Process. Lett. 25 (1987), no. 6,
369–373. MR
905781, http://dx.doi.org/10.1016/00200190(87)902146
 [8]
Daniel
Dominic Sleator and Robert
Endre Tarjan, Selfadjusting binary search trees, J. Assoc.
Comput. Mach. 32 (1985), no. 3, 652–686. MR 796206
(87a:68032), http://dx.doi.org/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
(89a:68045), http://dx.doi.org/10.1145/30401.315747
 [10]
Robert
Endre Tarjan, Data structures and network algorithms, CBMSNSF
Regional Conference Series in Applied Mathematics, vol. 44, Society
for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1983. MR 826534
(87g:68029)
 [11]
W. P. Thurston and J. R. Weeks, The mathematics of threedimensional manifolds, Scientific American 251 (1984), 108120.
 [12]
W. P. Thurston, The geometry and topology of threedimensional 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), 2632.
 [15]
Hassler
Whitney, A theorem on graphs, Ann. of Math. (2)
32 (1931), no. 2, 378–390. MR
1503003, http://dx.doi.org/10.2307/1968197

 [1]
 H. M. S. Coxeter, NonEuclidean 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), 3942. MR 678031 (83k:68059)
 [3]
 A. K. Dewdney, Wagner's theorem for torus graphs, Discrete Math. 4 (1973), 139149. 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, AddisonWesley, Reading, MA, 1973. MR 0445948 (56:4281)
 [6]
 J. Milnor, Hyperbolic geometry: the first 150 years, Bull. Amer. Math. Soc. 6 (1982), 924. MR 634431 (82m:57005)
 [7]
 J. Pallo, On rotation distance in the lattice of binary trees, Inform. Process. Lett. 25 (1987), 369373. MR 905781
 [8]
 D. D. Sleator and R. E. Tarjan, Selfadjusting binary search trees, J. Assoc. Comput. Mach. 32 (1985), 652686. 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 2830, 1986, Berkeley, CA, Association for Computing Machinery, NY, pp. 122135. 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 threedimensional manifolds, Scientific American 251 (1984), 108120.
 [12]
 W. P. Thurston, The geometry and topology of threedimensional manifolds, Princeton Univ., Dept. of Math., 1979.
 [13]
 W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956), 99116. MR 0081471 (18:408e)
 [14]
 K. Wagner, Bemerkungen zum Vierfarbenproblem, J. Deutschen Math.Verein. 46 (1936), 2632.
 [15]
 H. Whitney, A theorem on graphs, Ann. of Math. 32 (1931), 378390. 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
Daniel D. Sleator
Affiliation:
Robert E. Tarjan
Affiliation:
William P. Thurston
Affiliation:
DOI:
http://dx.doi.org/10.1090/S08940347198809289044
PII:
S 08940347(1988)09289044
Article copyright:
© Copyright 1988 American Mathematical Society
