**Figure:** Two different triangulations of a given convex seven-gon

A *triangulation* of a polygon
is a set of non-intersecting diagonals
that partitions the polygon into triangles.
We say that the *weight* of a triangulation is the sum
of the lengths of its diagonals.
As shown in Figure , any given polygon may
have many different triangulations.
For any given polygon, we seek to find its minimum weight triangulation.
Triangulation is a fundamental component of most geometric algorithms,
as discussed in Section .

To apply dynamic programming, we need a way to carve up the polygon into smaller pieces. A first idea might be to try all possible chords, each of which partitions the polygon into two smaller polygons. Using dynamic programming, this will work to give a polynomial-time algorithm. However, there is a slicker approach.

**Figure:** Selecting the vertex *k* to pair with an edge (*i*,*j*) of the polygon

Observe that every edge of the input polygon must be involved in
exactly one triangle.
Turning this edge into a triangle means identifying
the third vertex, as shown in Figure .
Once we find the correct connecting vertex, the polygon will be partitioned
into two smaller pieces, both of which need to be triangulated optimally.
Let *T*[*i*,*j*] be the cost of triangulating from vertex to vertex ,
ignoring the length of the chord from to .
The latter clause avoids double counting these internal chords in the
following recurrence:

The basis condition applies when *i* and *j* are immediate neighbors,
as *T*[*i*,*i*+1] = 0.

Since the number of vertices in each subrange of the right side of the
recurrence is smaller than that on the left side,
evaluation can proceed in terms of the gap size from *i* to *j*:

Minimum-Weight-Triangulation(

P)for

i=1 tondoT[i,j]=0for

gap=1 ton-1for

i=1 ton-gapdo

j=i+gap

return

T[1,n]

There are values of *T*,
each of which takes *O*(*j*-*i*) time if we evaluate the sections in order
of increasing size.
Since *j*-*i* = *O*(*n*), complete evaluation takes time and
space.

What if there are points in the interior of the polygon? Then dynamic programming does not apply in the same way, because each of the triangulation edges does not necessarily cut the boundary into two distinct pieces as before. Instead of only possible subregions, the number of subregions now grows exponentially. In fact, no efficient algorithm for this problem is known. More surprisingly, there is also no known proof of hardness. Minimum weight triangulation is one of the few well-studied algorithmic problems that remain in this limbo state.

Mon Jun 2 23:33:50 EDT 1997