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. Could you guys look at my
algorithm and tell me if I'm 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]
    

**EDIT:** 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
    


Answer: 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](http://geeksonjava.com/interview/fibonacci.php), 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.

