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.
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.
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.
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
n
n
2n-10
n\geq13
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
5.2n-33.6
7n/3+\Theta(1)
The flip distance between triangulations of a convex polygon is equivalent to the rotation distance between two binary trees.
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.
Let be the number of points in the point set and be the flip distance. The current best FPT algorithm runs in
O(n+k ⋅ 32k)
O(3.82k)
If no five points of a point set form an empty pentagon, there exists a
O(n2)