Rotation distance

Rotation distance was first defined by Karel Čulík II and Derick Wood in 1982.

Several self-balancing binary search tree data structures use these rotations as a primitive operation in their rebalancing algorithms.

There is a one-to-one correspondence between triangulations of a given convex polygon, with a designated root edge, and binary trees, taking triangulations of n-sided polygons into binary trees with n − 2 nodes.

The root node is the triangle having the designated root edge as one of its sides, and two nodes are linked as parent and child in the tree when the corresponding triangles share a diagonal in the triangulation.

In terms of triangulations of convex polygons, the right spine is the sequence of triangles incident to the right endpoint of the root edge, and the tree in which all vertices lie on the spine corresponds to a fan triangulation for this vertex.

[2] Sleator, Tarjan & Thurston (1988) also used a geometric argument to show that, for infinitely many values of n, the maximum rotation distance is exactly 2n − 6.

They find a family of polyhedra with the property that (in three-dimensional hyperbolic geometry) the polyhedra have large volume, but all tetrahedra inside them have much smaller volume, implying that many tetrahedra are needed in any triangulation.

[2] Subsequently, Pournin (2014) provided a proof that for all n ≥ 11, the maximum rotation distance is exactly 2n − 6.

[4] A similar approach of partitioning into subproblems along shared diagonals leads to a fixed-parameter tractable algorithm for computing the rotation distance exactly.

[5][6] Determining the complexity of computing the rotation distance exactly without parameterization remains unsolved, and the best algorithms currently known for the problem run in exponential time.

In abstract algebra, each element in Thompson's group F has a presentation using two generators.

Fordham's algorithm computes the rotation distance under this restriction in linear time.

Both variants result in a meet semi-lattice, whose structure is exploited to derive a