Minimum Weight Triangulation Dynamic Programming Algorithm

Question

So, I'm trying to understand the dynamic programming algorithm for finding the minimum weighted triangulation decomposition of a convex polygon. For those of you that don't know, triangulation is where we take a convex polygon, and break it up into triangles. The minimum weighted triangulation is the triangulation of a polygon where the sum of all the edges(or perimeter of every triangle) is the smallest.

It's actually a fairly common algorithm, however I just can't grasp it. Here is the algorithm I'm trying to understand:

http://en.wikipedia.org/wiki/Minimum-weight_triangulation#Variations

Here's another description I'm trying to follow(Scroll down to 5.2 Optimal Triangulations):

http://valis.cs.uiuc.edu/~sariel/teach/notes/algos/lec/05_dprog_II.pdf

So I understand this much so far. I take all my vertices, and make sure they are in clockwise order around the perimeter of the original polygon. I make a function that returns the minimum weight triangulation, which I call MWT(i, j) of a polygon starting at vertex i and going to vertex j. This function will be recursive, so the first call should be MWT(0, n-1), where n is the total number of vertices. MWT should test all the triangles that are made of the points i, j, and k, where k is any vertex between those. Here's my code so far:

def MWT(i, j):
    if j <= i: return 0
    elif j == i+1: return 0

    cheap_cost = float("infinity")
    for k in range(i, j):
        cheap_cost = min(cheap_cost, cost((vertices[i], vertices[j], vertices[k])) + MWT(i, k) + MWT(k, j))
    return cheap_cost

However when I run it it overflows the stack. I'm just completely lost and would appreciate if somebody could help direct me in the right direction.

If you guys need any more info just ask.

I don't think it's a typo in my code, I just think I'm not getting the gist of the algorithm, if you understand it could you just explain what the algorithm is doing? — robins35

Xymostech Xymostech · Accepted Answer · 2013-03-03T03:34:02

I think that you want to do

for k in range(i+1, j):

not

for k in range(i, j):

because you never want k to be the same as i or j (otherwise you'll just calculate it for the same values that you're currently running).

Minimum Weight Triangulation Dynamic Programming Algorithm

1 Answers