Flip distance

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.

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.

[3] 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.

[6][3] Whether all flip graphs of finite 3- or 4-dimensional point sets are connected is an open problem.

-gon has been obtained by Daniel Sleator, Robert Tarjan, and William Thurston[8] when

For instance Klaus Wagner provided a quadratic upper bound on the diameter of the flip graph of a set of

[11] 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.

[8] Computing the flip distance between triangulations of a point set is both NP-complete and APX-hard.

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

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

[17] A faster FPT algorithm exists for the flip distance between convex polygon triangulations; it has time complexity

algorithm for the flip distance between triangulations of this point set.