Geodesic
Rotation distance, triangulations, and hyperbolic geometry
Journal of the American Mathematical Society, Tome 01 (1988) no. 3, pp. 647-681

Voir la notice de l'article provenant de la source American Mathematical Society

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. 
@article{10_1090_S0894_0347_1988_0928904_4,
     author = {Sleator, Daniel D. and Tarjan, Robert E. and Thurston, William P.},
     title = {Rotation distance, triangulations, and hyperbolic geometry},
     journal = {Journal of the American Mathematical Society},
     pages = {647--681},
     publisher = {mathdoc},
     volume = {01},
     number = {3},
     year = {1988},
     doi = {10.1090/S0894-0347-1988-0928904-4},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1988-0928904-4/}
}
TY  - JOUR
AU  - Sleator, Daniel D.
AU  - Tarjan, Robert E.
AU  - Thurston, William P.
TI  - Rotation distance, triangulations, and hyperbolic geometry
JO  - Journal of the American Mathematical Society
PY  - 1988
SP  - 647
EP  - 681
VL  - 01
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1988-0928904-4/
DO  - 10.1090/S0894-0347-1988-0928904-4
ID  - 10_1090_S0894_0347_1988_0928904_4
ER  - 
%0 Journal Article
%A Sleator, Daniel D.
%A Tarjan, Robert E.
%A Thurston, William P.
%T Rotation distance, triangulations, and hyperbolic geometry
%J Journal of the American Mathematical Society
%D 1988
%P 647-681
%V 01
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1988-0928904-4/
%R 10.1090/S0894-0347-1988-0928904-4
%F 10_1090_S0894_0347_1988_0928904_4
Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. Rotation distance, triangulations, and hyperbolic geometry. Journal of the American Mathematical Society, Tome 01 (1988) no. 3, pp. 647-681. doi: 10.1090/S0894-0347-1988-0928904-4

[1] Coxeter, H. S. M. Non-Euclidean Geometry 1942

[2] Culik, Karel, Ii, Wood, Derick A note on some tree similarity measures Inform. Process. Lett. 1982 39 42

[3] Dewdney, A. K. Wagner’s theorem for torus graphs Discrete Math. 1973 139 149

[4] Gardner, Martin Time travel and other mathematical bewilderments 1988

[5] Knuth, Donald E. The art of computer programming. Volume 3 1973

[6] Milnor, John Hyperbolic geometry: the first 150 years Bull. Amer. Math. Soc. (N.S.) 1982 9 24

[7] Pallo, Jean On the rotation distance in the lattice of binary trees Inform. Process. Lett. 1987 369 373

[8] Sleator, Daniel Dominic, Tarjan, Robert Endre Self-adjusting binary search trees J. Assoc. Comput. Mach. 1985 652 686

[9] Ryabko, B. Ya., Horspool, R. Nigel, Cormack, Gordon V. Comments to: “A locally adaptive data compression scheme” [Comm. ACM 29 (1986), no. 4, 320–330 Comm. ACM 1987 792 794

[10] Tarjan, Robert Endre Data structures and network algorithms 1983

[11] Tutte, W. T. A theorem on planar graphs Trans. Amer. Math. Soc. 1956 99 116

[12] Whitney, Hassler A theorem on graphs Ann. of Math. (2) 1931 378 390

Cité par Sources :