next up previous
Next: Optimal grouping of a Up: The problems Previous: The problems

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.2Let $ 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:

    $\displaystyle 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.

next up previous
Next: Optimal grouping of a Up: The problems Previous: The problems
Danny Heap 2002-11-27