Flip distance

Template:Short description In discrete mathematics and theoretical computer science, the flip distance between two triangulations of the same point set is the number of flips required to transform one triangulation into another. A flip removes an edge between two triangles in the triangulation and then adds the other diagonal in the edge's enclosing quadrilateral, forming a different triangulation of the same point set.

This problem is known to be NP-hard. However, the computational complexity of determining the flip distance between convex polygons, a special case of this problem, is unknown. Computing the flip distance between convex polygon triangulations is also equivalent to rotation distance, the number of rotations required to transform one binary tree into another.

Definition

The flip graphs of a pentagon and a hexagon

Given a family of triangulations of some geometric object, a flip is an operation that transforms one triangulation to another by removing an edge between two triangles and adding the opposite diagonal to the resulting quadrilateral. The flip distance between two triangulations is the minimum number of flips needed to transform one triangulation into another. It can also be described as the shortest path distance in a flip graph, a graph that has a vertex for each triangulation and an edge for each flip between two triangulations. Flips and flip distances can be defined in this way for several different kinds of triangulations, including triangulations of sets of points in the Euclidean plane, triangulations of polygons, and triangulations of abstract manifolds.

Feasibility

The flip distance is well-defined only if any triangulation can be converted to any other triangulation via a sequence of flips. An equivalent condition is that the flip graph must be connected.

In 1936, Klaus Wagner showed that maximal planar graphs on a sphere can be transformed to any other maximal planar graph with the same vertices through flipping. A. K. Dewdney generalized this result to triangulations on the surface of a torus while Charles Lawson to triangulations of a point set on a 2-dimensional plane.

For triangulations of a point set in dimension 5 or above, there exists examples where the flip graph is disconnected and a triangulation cannot be obtained from other triangulations via flips. Whether all flip graphs of finite 3- or 4-dimensional point sets are connected is an open problem.

Diameter of the flip graph

The maximum number of flips required to transform a triangulation into another is the diameter of the flip graph. The diameter of the flip graph of a convex $n$-gon has been obtained by Daniel Sleator, Robert Tarjan, and William Thurston when $n$ is sufficiently large and by Lionel Pournin for all $n$. This diameter is equal to $2n-10$ when $n\ge 13$.

The diameter of other flip graphs has been studied. For instance Klaus Wagner provided a quadratic upper bound on the diameter of the flip graph of a set of $n$ unmarked points on the sphere. The current upper bound on the diameter is $5n-23$, while the best-known lower bound is $7n/3+\mathrm{\Theta }(1)$. The diameter of the flip graphs of arbitrary topological surfaces with boundary has also been studied and their exact value is known in several cases.

Equivalence with other problems

The flip distance between triangulations of a convex polygon is equivalent to the rotation distance between two binary trees.

Computational complexity

Computing the flip distance between triangulations of a point set is both NP-complete and APX-hard. However, it is fixed-parameter tractable (FPT), and several FPT algorithms that run in exponential time have been proposed.

Computing the flip distance between triangulations of a simple polygon is also NP-hard.

The complexity of computing the flip distance between triangulations of a convex polygon remains an open problem.

Algorithms

Let Template:Mvar be the number of points in the point set and Template:Mvar be the flip distance. The current best FPT algorithm runs in $O(n+k\cdot 32^k)$. A faster FPT algorithm exists for the flip distance between convex polygon triangulations; it has time complexity $O(3.82^k)$

If no five points of a point set form an empty pentagon, there exists a $O(n^2)$ algorithm for the flip distance between triangulations of this point set.

See also

• Associahedron
• Flip graph
• Rotation distance
• Tamari lattice