The Algorithm Design Manual Second Edition

8.6.1

Minimum Weight Triangulation

The same basic recurrence relation encountered in the parsing algorithm above can

also be used to solve an interesting computational geometry problem. A triangu-

lation of a polygon P =

{v

1

, . . . , v

n

, v

1

} is a set of nonintersecting 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

8.10

, any given poly-

gon may have many different triangulations. We seek to find its minimum weight

triangulation for a given polygon p. Triangulation is a fundamental component of

most geometric algorithms, as discussed in Section

17.3

(page

572

).

To apply dynamic programming, we need a way to carve up the polygon into

smaller pieces. 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

8.11

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

i

to

vertex v

j

, ignoring the length of the chord d

ij

from v

i

to v

j

. The latter clause

avoids double counting these internal chords in the following recurrence:

T [i, j]

=

j

−1

min

k=i+1

(T [i, k] + T [k, j] + d

ik

+ d

kj

)

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

---

8 . 7

L I M I T A T I O N S O F D Y N A M I C P R O G R A M M I N G : T S P

301

i

j

k

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

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 to n

− 1 do T [i, i + 1] = 0

for gap = 2 to n

− 1

for i = 1 to n

− gap do

j = i + gap

T [i, j] = min

j

−1

k=i+1

(T [i, k] + T [k, j] + d

P

i

,P

k

+ d

P

k

,P

j

)

return T [1, n]

There are



n

2



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

O(n

3

) time and O(n

2

) space.

What if there are points in the interior of the polygon? Then dynamic pro-

gramming does not apply in the same way, because triangulation edges do not

necessarily cut the boundary into two distinct pieces as before. Instead of only



n

2



possible subregions, the number of subregions now grows exponentially. In fact, the

more general version of this problem is known to be NP-complete.

Take-Home Lesson:

For any optimization problem on left-to-right objects,

such as characters in a string, elements of a permutation, points around a

polygon, or leaves in a search tree, dynamic programming likely leads to an

efficient algorithm to find the optimal solution.