Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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).
There are two parts to understanding here.
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
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.
