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.
@cite_18: Abstract In this paper we prove that it is possible to transform every triangulation of a set points inside a polygonal domain in the plane into every other triangulation of the same set of points using only operations of swapping diagonals in convex quadrilaterals.
@cite_13: Publisher Summary This chapter discusses algorithm and underlying theory of software for C1 surface interpolation. There has been practically no theory to guide the development of algorithms for triangulation and there has been no practical static global criterion to characterize a preferred triangulation. An interpolation algorithm is interfaced with algorithms for contour plotting or surface perspective plotting. If the subroutines are available for doing contour or surface perspective plotting for data given on a rectangular grid, then the surface interpolation algorithm can be used to produce the values needed at the lattice points of a rectangular grid. The computerized representation of surfaces is a central issue in the field of computer-aided geometric design and plays an important role in the field of finite element methods. Some methods of building a triangular grid with a given set of nodes start by locating the boundary points of the convex hull of the point set. In some reasonable triangulation algorithms, the number of boundary points of the convex hulls of a sequence of sub­sets has an effect on the operation count.
@cite_3: 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.
Flips have been studied in more general settings as well. @cite_18 proved that any two triangulations of a simple polygon can be transformed into one another using flips. They proved that the same holds even for two triangulations of a simple polygon with points inside it. The latter is also known in the literature as a , or simply a . This is because the graph whose nodes correspond to the points and edges correspond to the edges of the triangulation and of the polygon is a maximal planar graph (also called a triangulation) where one particular face is not necessarily a triangle. Lawson @cite_13 proved an upper bound of @math flips needed in any such flip sequence. @cite_3 proved that the bound is tight asymptotically.