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. 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. It is not known whether the minimum-weight triangulation decision problem is NP-complete, since this depends on the known open problem whether the sum of radicals may be computed in polynomial time. However, Mulzer and Rote remark that the problem is NP-complete if the edge weights are rounded to integer values. Although NP-hard, the minimum weight triangulation may be constructed in subexponential time by a dynamic programming algorithm that considers all possible simple cycle separators of O ( n ) {displaystyle O({sqrt {n}})} points within the triangulation, recursively finds the optimal triangulation on each side of the cycle, and chooses the cycle separator leading to the smallest total weight. The total time for this method is 2 O ( n log ⁡ n ) {displaystyle 2^{O({sqrt {n}}log n)}} . Several authors have proven results relating the minimum weight triangulation to other triangulations in terms of the approximation ratio, the worst-case ratio of the total edge length of the alternative triangulation to the total length of the minimum weight triangulation. In this vein, it is known that the Delaunay triangulation has an approximation ratio of Θ ( n ) {displaystyle Theta (n)} , and that the greedy triangulation (the triangulation formed by adding edges in order from shortest to longest, at each step including an edge whenever it does not cross an earlier edge) has an approximation ratio of Θ ( n ) {displaystyle Theta ({sqrt {n}})} . Nevertheless, for randomly distributed point sets, both the Delaunay and greedy triangulations are within a logarithmic factor of the minimum weight. The hardness result of Mulzer and Rote also implies the NP-hardness of finding an approximate solution with relative approximation error at most O(1/n2). Thus, a fully polynomial approximation scheme for minimum weight triangulation is unlikely. However, a quasi-polynomial approximation scheme is possible: for any constant ε > 0, a solution with approximation ratio 1 + ε can be found in quasi-polynomial time exp(O((log n)9). Because of the difficulty of finding the exact solutions of the minimum-weight triangulation, many authors have studied heuristics that may in some cases find the solution although they cannot be proven to work in all cases. In particular, much of this research has focused on the problem of finding sets of edges that are guaranteed to belong to the minimum-weight triangulation. If a subgraph of the minimum-weight triangulation found in this way turns out to be connected, then the remaining untriangulated space may be viewed as forming a simple polygon, and the entire triangulation may be found by using dynamic programming to find the optimal triangulation of this polygonal space. The same dynamic programming approach can also be extended to the case that the subgraph has a bounded number of connected components and the same approach of finding a connected graph and then applying dynamic programming to fill in the polygonal gaps surrounding the graph edges has also been used as part of heuristics for finding low-weight but not minimum-weight triangulations.