Given two triangulations of a convex polygon, computing the minimum number of flips required to transform one to the other is a long-standing open problem. It is not known whether the problem is in P or NP-complete. We prove that two natural generalizations of the problem are NP-complete, namely computing the minimum number of flips between two triangulations of (1) a polygon with holes; (2) a set of points in the plane.
Flip distance between triangulations of a convex polygon and rotation distance between binary trees have been well studied in the past. Several results deal with the combinatorics of the flip operation. @cite_20 proved that for large values of @math , the flip distance between two triangulations of an @math -gon is at most @math and that occasionally @math flips are necessary. Other results deal with the , i.e., the graph where nodes correspond to triangulations of an @math -gon and an edge between two nodes denotes the fact that the corresponding triangulations are one flip apart. For example, Lucas @cite_5 showed that the flip graph is hamiltonian. See also Eppstein @cite_15 .
@cite_5 @cite_15 @cite_20
2163548699 2029387472 2110762325 1987750368
Let T be a triangulation of a simple polygon. A flip in T is the operation of replacing one diagonal of T by a different one such that the resulting graph is again a triangulation. The flip distance between two triangulations is the smallest number of flips required to transform one triangulation into the other. For the special case of convex polygons, the problem of determining the shortest flip distance between two triangulations is equivalent to determining the rotation distance between two binary trees, a central problem which is still open after over 25 years of intensive study. We show that computing the flip distance between two triangulations of a simple polygon is NP-hard. This complements a recent result that shows APX-hardness of determining the flip distance between two triangulations of a planar point set. In this paper we study the problem of flipping edges in triangulations of polygons and point sets. One of the main results is that any triangulation of a set of n points in general position contains at least ( (n-4) 2 ) edges that can be flipped. We also prove that O(n + k 2 ) flips are sufficient to transform any triangulation of an n -gon with k reflex vertices into any other triangulation. We produce examples of n -gons with triangulations T and T' such that to transform T into T' requires Ω(n 2 ) flips. Finally we show that if a set of n points has k convex layers, then any triangulation of the point set can be transformed into any other triangulation using at most O(kn) flips. Given two triangulations of a convex polygon, computing the minimum number of flips required to transform one to the other is a long-standing open problem. It is not known whether the problem is in P or NP-complete. We prove that two natural generalizations of the problem are NP-complete, namely computing the minimum number of flips between two triangulations of (1) a polygon with holes; (2) a set of points in the plane. In this work we consider triangulations of point sets in the Euclidean plane, i.e., maximal straight-line crossing-free graphs on a finite set of points. Given a triangulation of a point set, an edge flip is the operation of removing one edge and adding another one, such that the resulting graph is again a triangulation. Flips are a major way of locally transforming triangular meshes. We show that, given a point set S in the Euclidean plane and two triangulations T"1 and T"2 of S, it is an APX-hard problem to minimize the number of edge flips to transform T"1 to T"2.