Minimum Weight Triangulation

Definitions

Given 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.

Some cost functions

• cost(e) = 1 for every edge e

  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 3n-3-k
  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...

The Minimum Weight Triangulation problem

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.

The MWT applet

Below is an applet where you can experiment with the Minimum Weight Triangulation.

• Click in the white area to add or drag points.
• Click with the other button or use a modifier key to delete points.
• MWT edges are blue when they are necessarily part of every triangulation, otherwise they are green.
• Don't create too many points! This applet is in Java and it's running an exponential algorithm!