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).

  • 2
    $\begingroup$ Are you familiar with dynamic programming? Have you seen proofs of dynamic programming algorithms? Do you understand equation (5)? $\endgroup$ – Yuval Filmus Apr 7 '13 at 4:38
  • $\begingroup$ I'm not familiar with the problem you refer to, and a Wikipedia search does not yield anything. Please describe the problem and/or link to a reference. $\endgroup$ – Raphael Apr 7 '13 at 12:39

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.