Minimum-weight 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.[2]

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 ${\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 ${\displaystyle 2^{O({\sqrt {n}}\log n)}}$.[3]

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 ${\displaystyle \Theta (n)}$,[4] 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 ${\displaystyle \Theta ({\sqrt {n}})}$.[5] Nevertheless, for randomly distributed point sets, both the Delaunay and greedy triangulations are within a logarithmic factor of the minimum weight.[6]

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/n²). 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)⁹).[7]

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[8] 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.[9]

The graph formed by connecting two points whenever they are each other's nearest neighbors is necessarily a subgraph of the minimum-weight triangulation.[10] However, this mutual nearest neighbor graph is a matching, and hence is never connected. A related line of research finds large subgraphs of the minimum-weight triangulation by using circle-based β-skeletons, the geometric graphs formed by including an edge between two points u and v whenever there does not exist a third point w forming an angle uwv greater than some parameter θ. It has been shown that, for sufficiently small values of θ, the graph formed in this way is a subgraph of the minimum-weight triangulation.[11] However, the choice of θ needed to ensure this is smaller than the angle {{{1}}} for which the β-skeleton is always connected.

A more sophisticated technique called the LMT-skeleton was proposed by Dickerson & Montague (1996). It is formed by an iterative process, in which two sets of edges are maintained, a set of edges known to belong to the minimum-weight triangulation and a set of edges that are candidates to belong to it. Initially, the set of known edges is initialized to the convex hull of the input, and all remaining pairs of vertices form candidate edges. Then, in each iteration of the construction process, candidate edges are removed whenever there is no pair of triangles formed by the remaining edges forming a quadrilateral for which the candidate edge is the shortest diagonal, and candidate edges are moved to the set of known edges when there is no other candidate edge that crosses them. The LMT-skeleton is defined to be the set of known edges produced after this process stops making any more changes. It is guaranteed to be a subgraph of the minimum-weight triangulation, can be constructed efficiently, and in experiments on sets of up to 200 points it was frequently connected.[12] However it has been shown that on the average for large point sets it has a linear number of connected components.[13]

Other heuristics that have been applied to the minimum weight triangulation problem include genetic algorithms[14] branch and bound,[15] and ant colony optimization algorithms.[16]

A polygon triangulation of minimal weight may be constructed in cubic time using the dynamic programming approach, reported independently by Gilbert (1979) and Klincsek (1980). In this method, the vertices are numbered consecutively around the boundary of the polygon, and for each diagonal from vertex i to vertex j that lies within the polygon, the optimal triangulation is calculated by considering all possible triangles ijk within the polygon, adding the weights of the optimal triangulations below the diagonals ik and jk, and choosing the vertex k that leads to the minimum total weight. That is, if MWT(i,j) denotes the weight of the minimum-weight triangulation of the polygon below edge ij, then the overall algorithm performs the following steps:

• For each possible value of i, from n − 1 down to 1, do:
  • For each possible value of j, from i + 1 to n, do:
    • If ij is an edge of the polygon, set MWT(i,j) = length(ij)
    • Else if ij is not an interior diagonal of the polygon, set MWT(i,j) = +∞
    • Else set MWT(i,j) = length(ij) + min_{i < k < j} MWT(i,k) + MWT(k,j)

After this iteration completes, MWT(1,n) will store the total weight of the minimum weight triangulation. The triangulation itself may be obtained by recursively searching through this array, starting from MWT(1,n), at each step choosing the triangle ijk that leads to the minimum value for MWT(i,j) and recursively searching MWT(i,k) and MWT(j,k).

Similar dynamic programming methods may also be adapted to point set inputs where all but a constant number of points lie on the convex hull of the input,[17] and to point sets that lie on a constant number of nested convex polygons or on a constant number of lines no two of which cross within the convex hull.[18]

It is also possible to formulate a version of the point set or polygon triangulation problems in which one is allowed to add Steiner points, extra vertices, in order to reduce the total edge length of the resulting triangulations. In some cases, the resulting triangulation may be shorter than the minimum weight triangulation by as much as a linear factor. It is possible to approximate the minimum weight Steiner triangulation of a point set to within a constant factor of optimal, but the constant factor in the approximation is large.[19]

Related problems that have also been studied include the construction of minimum-weight pseudotriangulations[20] and the characterization of the graphs of minimum-weight triangulations.[21]

• Minimum Weight Triangulation using an LMT Skeleton source code'