Minimum-weight triangulation
The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy.
The weight of a triangulation of a set of points in the Euclidean plane is defined as the sum of lengths of its edges.
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
[5] Nevertheless, for randomly distributed point sets, both the Delaunay and greedy triangulations are within a logarithmic factor of the minimum weight.
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.
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.
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.
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.
[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).
