Minimum Weight Triangulation

(An interactive introduction)

by François Labelle


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

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.

(Sorry, your browser does not support Java applets.)

last updated: June 5, 2006
go to François Labelle's Homepage