Rotation Distance, Triangulations, and Hyperbolic Geometry
Original Publication Date: 1988-Jan-31
Included in the Prior Art Database: 2007-Mar-29
Software Patent Institute
Sleator, Daniel D.: AUTHOR [+4]
Rotation Distance, I'riangulations, and Hyperboiic Geometry Daniel D. Sleator, Robert E. :f'jan, and William P. Thurston January 1988C MU-CS-88-108
Rotation Distance, I'riangulations, and Hyperboiic Geometry
Daniel D. Sleator, Robert E. :f'jan, and William P. Thurston January 1988
Partial support provided by DARPA, ARPA order 4976, amendment 19, monitored by the Air Force Avionics Laboratory undcr contract F33615-87-42-1499, and by the Na- tional Science Foudatian under grants CCR-8a38139, DCR-8605962, DMR-8504984 and DCR-83055
Rot:~tiun I)ist:;ncc, Triangulations, and Hypcrholic Geo~~letry
Computcr Science Departinent C;lrnegie Mellon University
Pittsburgh, PA 15213
Roben E. Tarjan
Computer Science Department
Princeton, NJ 08544
AT&T Bell Laboratories
Murray Hill, NJ 07974
U'illiant P. Thurston
blatf~ernatics Department Princeton IJnive~ity
Princeton, NJ 08544
A rotarion in a binary tree is a local restructuring that changes the tree into another tree. Rotations are usefbl in the design of tree-based tiat. structures. The rotation dis tnnce 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 ail large n, using 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
Ths is a revised and expanded version of a paper that appeared in the 18th Annual
ACM Symposium on Theory of Computing, .
Partial support provided by DARPA, ARPA order 4976, arnendrncnr 19, monitored by the Air Force Avionics Laboratory under cor~uact F33615-87-C-1499, and by the National Science Foundation under grant CCK-8658139.
Partial support provided by the National Science Foundation under grant DCR-8605962.
Partial support provided by the Nadonal Science Foundation under grants DMR-8504984 and DCR- 8505517.
among binary trees, triaup~lintions, pol!.hcdra, ;lnd hyperi~olic gomctry.
Pi rok-i/iotz in a binary tree is a local restructuring of the tree that changes it into another tree. One can execurc: a rotation by coll;~psing an internal edge of the tree to a point, thereby obtaining a node with three children, and then re-expanding the node of order three in the alternative way into two nodes of order 2. The roralion disfance between a pair of trees is the minimum numbcr of rotations necded to convert one tree into the other. The problen1 addressed in this paper is: what is the maximum rotation distance between any pair of n-node binary trees? We show that for all n 211 this dis- tance is at most 2n -6 and that for all sufficiently large it...