Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Rotation Distance, Triangulations, and Hyperbolic Geometry

IP.com Disclosure Number: IPCOM000148171D
Original Publication Date: 1988-Jan-31
Included in the Prior Art Database: 2007-Mar-29
Document File: 52 page(s) / 3M

Publishing Venue

Software Patent Institute

Related People

Sleator, Daniel D.: AUTHOR [+4]

Abstract

Rotation Distance, I'riangulations, and Hyperboiic Geometry Daniel D. Sleator, Robert E. :f'jan, and William P. Thurston January 1988C MU-CS-88-108 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 17. 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 UniversityPrinceton, NJ 08544andAT&T Bell Laboratories Murray Hill, NJ 07974 U'illiant P. Thurston blatf~ernatics Department Princeton IJnive~ity Princeton, NJ 08544 Abstract 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

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 4% of the total text.

Page 1 of 52

Rotation Distance, I'riangulations, and Hyperboiic Geometry

Daniel D. Sleator, Robert E. :f'jan, and William P. Thurston January 1988
C MU-CS-88-108

  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


17.

[This page contains 1 picture or other non-text object]

Page 2 of 52

[This page contains 1 picture or other non-text object]

Page 3 of 52

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 University
Princeton, NJ 08544
and
AT&T Bell Laboratories

Murray Hill, NJ 07974

U'illiant P. Thurston

blatf~ernatics Department Princeton IJnive~ity

Princeton, NJ 08544

Abstract

   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, [9].

 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.

I

[This page contains 1 picture or other non-text object]

Page 4 of 52

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...