Algorithm to minimize sum of diagonals for triangulation of convex polygon?

Define the cost of a triangulation as the sum of the lengths of the diagonals that have been added. Given a convex polygon, what is the cost of its cheapest triangulation? If we consider the polygon as a set of n coordinates: v_1=x_1,y_1,...,v_n=x_n,y_n and the solution must have n-3 diagonals (not overlapping because it's triangulation)

I have been trying to get the reccurence of this Dynamic programming problem but I can't seem to find a good one. I do not really recognize suboptimal structure to find the recurrence. Anyone could give me a hand on this?

The simplest method would be to iterate over every point, get the distance between the previous and the next point, and recurse with the polygon without the current point; e.g. for a pentagon abcde that would be:

• distance eb + recurse with quadrangle bcde
• distance ac + recurse with quadrangle cdea
• distance bd + recurse with quadrangle deab
• distance ce + recurse with quadrangle eabc
• distance da + recurse with quadrangle abcd

In order not to calculate the same solutions more than once, you should discard any solutions where points that have already been checked do not have a diagonal arriving in them; e.g. when recursing with quadrangle deab in step 3, the solution with a diagonal eb is a duplicate, because solutions that use triangle abe were already checked in the first step. Making no duplicate calculations at all may be complicated with this method.

Another method would be to choose a point (indicated in red in the illustration below), and then enumerate every solution as a number of digits whose sum is n - 2, where n is the number of points. The solution where every diagonal goes through the selected point would be solution 11111. Then, you run through every combination that sums to n - 2: 11111, 1112, 1121, 113, 1211, 122, 131, 14, 2111, 212, 221, 23, 311, 32, 41 and 5. A number greater than 1 means you combine 2 or more segments, and add the diagonal from its first to last point. When the number is greater than 2, this diagonal borders a left-over polygon (indicated in pink), which you recurse with.

The animation shows the iterations and recursions the algorithm goes through for a 7-point polygon, up until the point where it recurses with a 6-point polygon.

Both these methods offer possibilities for memoization and tabulation, but it won't be straightforward. A pentagon starting at point b isn't necessarily bcdef once you've started recursing; it might well be bdfhj. So retrieving stored intermediate results may get a bit complicated.