Minimum Weight Triangulation Taking Forever

Question

so I've been working on a program in Python that finds the minimum weight triangulation of a convex polygon. This means that it finds the weight(The sum of all the triangle perimeters), as well as the list of chords(lines going through the polygon that break it up into triangles, not the boundaries).

I was under the impression that I'm using the dynamic programming algorithm, however when I tried using a somewhat more complex polygon it takes forever(I'm not sure how long it takes because I haven't gotten it to finish).

It works fine with a 10 sided polygon, however I'm trying 25 and that's what is making it stall. My teacher gave me the polygons so I assume that the 25 one is supposed to work as well.

Since this algorithm is supposed to be O(n^3), the 25 sided polygon should take roughly 15.625 times longer to calculate, however it's taking way longer seeing that the 10 sided seems instantaneous.

Am I doing some sort of n operation in there that I'm not realizing? I can't see anything I'm doing, except maybe the last part where I get rid of the duplicates by turning the list into a set, however in my program I put a trace after the decomp before the conversion happens, and it's not even reaching that point.

Here's my code, if you guys need anymore info just please ask. Something in there is making it take longer than O(n^3) and I need to find it so I can trim it out.

#!/usr/bin/python
import math

def cost(v):
    ab = math.sqrt(((v[0][0] - v[1][0])**2) + ((v[0][1] - v[1][1])**2))
    bc = math.sqrt(((v[1][0] - v[2][0])**2) + ((v[1][1] - v[2][1])**2))
    ac = math.sqrt(((v[0][0] - v[2][0])**2) + ((v[0][1] - v[2][1])**2))
    return ab + bc + ac

def triang_to_chord(t, n):
    if t[1] == t[0] + 1:
        # a and b
        if t[2] == t[1] + 1:
            # single
            # b and c
            return ((t[0], t[2]), )
        elif t[2] == n-1 and t[0] == 0:
            # single
            # c and a
            return ((t[1], t[2]), )
        else:
            # double
            return ((t[0], t[2]), (t[1], t[2]))
    elif t[2] == t[1] + 1:
        # b and c
        if t[0] == 0 and t[2] == n-1:
            #single
            # c and a
            return ((t[0], t[1]), )
        else:
            #double
            return ((t[0], t[1]), (t[0], t[2]))
    elif t[0] == 0 and t[2] == n-1:
        # c and a
        # double
        return ((t[0], t[1]), (t[1], t[2]))
    else:
        # triple
        return ((t[0], t[1]), (t[1], t[2]), (t[0], t[2]))


file_name = raw_input("Enter the polygon file name: ").rstrip()
file_obj = open(file_name)
vertices_raw = file_obj.read().split()
file_obj.close()

vertices = []

for i in range(len(vertices_raw)):
    if i % 2 == 0:
        vertices.append((float(vertices_raw[i]), float(vertices_raw[i+1])))

n = len(vertices)

def decomp(i, j):
    if j <= i: return (0, [])
    elif j == i+1: return (0, [])

    cheap_chord = [float("infinity"), []]
    old_cost = cheap_chord[0]
    smallest_k = None

    for k in range(i+1, j):
        old_cost = cheap_chord[0]
        itok = decomp(i, k)
        ktoj = decomp(k, j)
        cheap_chord[0] = min(cheap_chord[0], cost((vertices[i], vertices[j], vertices[k])) + itok[0] + ktoj[0])
        if cheap_chord[0] < old_cost:
            smallest_k = k
            cheap_chord[1] = itok[1] + ktoj[1]

    temp_chords = triang_to_chord(sorted((i, j, smallest_k)), n)
    for c in temp_chords:
        cheap_chord[1].append(c)
    return cheap_chord

results = decomp(0, len(vertices) - 1)
chords = set(results[1])
print "Minimum sum of triangle perimeters = ", results[0]
print len(chords), "chords are:"
for c in chords:
    print "   ", c[0], "  ", c[1]

I'll add the polygons I'm using, again the first one is solved right away, while the second one has been running for about 10 minutes so far.

FIRST ONE:

202.1177      93.5606
177.3577     159.5286
138.2164     194.8717
73.9028     189.3758
17.8465     165.4303
2.4919      92.5714
21.9581      45.3453
72.9884       3.1700
133.3893      -0.3667
184.0190      38.2951

SECOND ONE:

397.2494     204.0564
399.0927     245.7974
375.8121     295.3134
340.3170     338.5171
313.5651     369.6730
260.6411     384.6494
208.5188     398.7632
163.0483     394.1319
119.2140     387.0723
76.2607     352.6056
39.8635     319.8147
8.0842     273.5640
-1.4554     226.3238
8.6748     173.7644
20.8444     124.1080
34.3564      87.0327
72.7005      46.8978
117.8008      12.5129
162.9027       5.9481
210.7204       2.7835
266.0091      10.9997
309.2761      27.5857
351.2311      61.9199
377.3673     108.9847
390.0396     148.6748

Nuclearman Nuclearman · Accepted Answer · 2013-03-05T10:39:36

It looks like you have an issue with the inefficient recurision here.

...
def decomp(i, j):
...
for k in range(i+1, j):
    ...
    itok = decomp(i, k)
    ktoj = decomp(k, j)
    ...
...

You've ran into the same kind of issue as a naive recursive implementation of the Fibonacci Numbers, but the way this algorithm works, it'll probably be much worst on the run time. Assuming that is the only issue with you're algorithm, then you just need to use memorization to ensure that the decomp is only calculated once for each unique input.

The way to spot this issue is to print out the values of i, j and k as the triple (i,j,k). In order to obtain a runtime of O(N^3), you shouldn't see the same exact triple twice. However, the triple (22, 24, 23), appears at least twice (in the 25), and is the first such duplicate. That shows the algorithm is calculating the same thing multiple times, which is inefficient, and is bumping up the performance well past O(N^3). I'll leave figuring out what the algorithms actual performance is to you as an exercise. Assuming there isn't something else wrong with the algorithm the algorithm should eventually stop.

Minimum Weight Triangulation Taking Forever

1 Answers