[Solved]: Proving correctness of the algorithm for convex polygon minimum cost triangulation

Problem Detail: 

I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be proven by induction but I struggle at choosing the right quantity to look at and also at the inductive step portion of the proof.

For example, can you provide a formal proof for the algorithm described here (page 5 problem 6.12).

Asked By : 372

Answered By : Raphael

There are two parts to understanding here.

1. The algorithm is a straight-forward implementation of equation (5) using memoisation.

2. Equation (5) is correct, that is $A[i,j]$ is

   the minimum cost triangulation of the polygon spanned by vertices $i,i+1,...,j$

   as the author claims. They give a reasoning right there:

   Formulating the subproblem this way we are enumerating all the possible diagonals such that the diagonals do not cross each other. Since we are only considering in clockwise directions, diagonals generated by the subproblems can not cross each other.

   They argue that

   • all feasible solutions are considered and
   • all considered solutions are feasible.

   If this is true, then choosing the minimum out all considered solutions is clearly the correct answer. Proving the bullets now needs insight into the problem, and the author gives the basic idea.

   In terms of an induction, what I sketch above amounts to the inductive step. The anchor is trivial and covered in the text. The induction hypothesis has to be phrased such that you know for $i,j$ fixed that all $A[i,k]$ and $A[k,j]$ for $k=i,\dots,j$ are optimal.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11085