n points in the plane, a triangulation is a maximal set of edges between pairs of points such that no edge properly intersect another edge or a point. In general, the number of possible triangulations is exponential in
n. If the edges have costs, then a minimum cost triangulation will be a triangulation in which the total cost of the edges is minimum.
cost(e) = 1for every edge
It is a well known fact that any triangulation has exactly
3n-3-k edges, where
k is the number of points lying on the convex hull of the set of points.
every triangulation has a cost of
every triangulation is a minimum cost triangulation
finding a minimum cost triangulation is trivial
cost(e) = 1 or 2
It is NP-complete to decide whether a triangulation exists or not when some edges are disallowed [Lloyd, 1977]. This is the same as giving a cost of
1 to allowed edges, and a cost of
2 to disallowed edges and asking whether a triangulation of cost
3n-3-k exists or not.
finding a minimum cost triangulation is NP-complete
cost(e) = length(e)
This simple choice of a cost function happens to be quite evil. The cost function is too weird to make it easy to find a minimum cost triangulation in polynomial time, yet the cost function is too strict to allow an easy NP-completeness proof...
When the cost of an edge is its length, a minimum cost triangulation is called a Minimum Length Triangulation, or more popularly (and less logically), a Minimum Weight Triangulation (MWT). Finding a Minimum Weight Triangulation is one of the few natural problems whose complexity remain unknown.
UPDATE (June 5, 2006): "Minimum Weight Triangulation is NP-Hard", W. Mulzer and G. Rote. Proceedings of the 22nd Annual Symposium on Computational Geometry, p1-10.
Below is an applet where you can experiment with the Minimum Weight Triangulation.