Minimal triangulation of a convex polygon

A convex polygon has interior angles that are each strictly less than 180$^\circ$ (or $\pi$ radians, if you like). A triangulation of a convex polygon is formed by drawing diagonals between non-adjacent vertices (corners), provided you never intersect another diagonal (except at a vertex), until all possible choices of diagonals have been used (see Figure 1).

Figure: Two triangulations of the same convex pentagon. The triangulation on the left has a cost of $8$ $+$ $2\sqrt {2}$ $+$ $2\sqrt {5}$ (approximately 15.30), the one on the right has a cost of $4$ $+$ $2\sqrt {2}$ $+$ $4\sqrt {5}$ (approximately 15.77). If you index the vertices counter-clockwise from $(0,0)$ (vertex 0) to $(0,2)$ (vertex $4$), then you could specify the triangulation on the left by listing the indices of its component triangles: 0 3 4, 0 1 3, and 1 2 3. You could specify the triangulation on the right similarly: 0 3 4, 0 2 3, 0 1 2.

Suppose a convex polygon has vertices $v_0$, $\ldots$, $v_n$. In any triangulation we can assign a weight to each triangle: the length of its perimeter.²Let $w(i,j,k)$ denote the length of the perimeter of $\bigtriangleup v_i v_j v_k$. The cost of a triangulation is just the sum of the weights of its component triangles. We want to find a triangulation with the minimum cost.

Here's a sketch of how to find a minimum cost triangulation of a convex polygon with $n+1$ vertices:

1. Number the vertices of your polygon from 0 to $n$.

2. Denote the cost of a minimal triangulation (which you haven't yet found) of your polygon as $c[0][n]$. Similarly, your polygon contains sub-polygons with vertices $i$ through $k$ (if $k$ is at least 2 greater than $i$), and you can denote the weight of a minimal triangulation of such a sub-polygon as $c[i][k]$.

3. Possible values of $c[i][k]$ fall into two cases. Case one: if $k$ $<$ $i+2$ then the polygon with vertices $v_i$ $\ldots$ $v_k$ has fewer than 3 vertices, and no triangulation is possible, so an appropriate minimum triangulation cost is 0. Case two: if $k$ $\geq$ $i+2$, then there are one or more choices of $j$ where $i$ $<$ $j$ $<$ $k$. For each choice of $j$, calculate $c[i][j]$ $+$ $c[j][k]$ $+$ $w(i,j,k)$ -- the minimum over all appropriate $j$ is $c[i][k]$. These two cases give the following recursive formula:

   $$c[i][k] = \begin{cases}0 & k < i + 2 \min_{i < j < k} \{c[i][j] + c[j][k] + w(i,j,k)\} & \text{otherwise} \end{cases}$$ (1)

   
   
   Record which index $j$ corresponds to the minimum (you might denote it $m[i][k]$).

4. Suppose $m[0][n]$ is denoted $j_0$, then you know that $\bigtriangleup v_0 v_{j_0} v_n$ is part of a minimal triangulation. You can find more triangles in this minimal triangulation using $m[0][j_0]$ and $m[j_0][n]$. Continue until you've found all triangles in a minimal triangulation.

Although it is possible to build up a table of values $c[i][k]$ iteratively (as described in your course notes), for this assignment you must find $c[0][n]$ recursively, using memoization (mentioned in lecture) to prevent redundant calculations of the same value.