Minimum-weight triangulation

In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.

The problem of minimum weight triangulation of a point set was posed by Düppe & Gottschalk (1970), who suggested its application to the construction of triangulated irregular network models of land countours, and used a greedy heuristic to approximate it. Shamos & Hoey (1975) conjectured that the minimum weight triangulation always coincided with the Delaunay triangulation, but this was quickly disproved by Lloyd (1977), and indeed Kirkpatrick (1980) showed that the weights of the two triangulations can differ by a linear factor.

The minimum-weight triangulation problem became notorious when Garey & Johnson (1979) included it in a list of open problems in their book on NP-completeness, and many subsequent authors published partial results on it. Finally, Mulzer & Rote (2008) showed it to be NP-hard, and Remy & Steger (2009) showed that accurate approximations to it can be constructed efficiently.

The weight of a triangulation of a set of points in the Euclidean plane is defined as the sum of lengths of its edges. Its decision variant is the problem of deciding whether there exists a triangulation of weight less than a given weight; it was proven to be NP-hard by Mulzer & Rote (2008). Their proof is by reduction from PLANAR-1-IN-3-SAT, a special case of the Boolean satisfiability problem in which a 3-CNF whose graph is planar is accepted when it has a truth assignment that satisfies exactly one literal in each clause. The proof uses complex gadgets, and involves computer assistance to verify the correct behavior of these gadgets.

...
Wikipedia