# Minimum Weight Triangulation

### (An interactive introduction)

by François Labelle

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

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

• 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!

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