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

- 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