Minimum Cost Triangulation

Let p1, . . . , pn be the clockwise ordering of the vertices of a convex polygon P. You are also given access to a constant time subroutine d(pi , pj ) which returns the distance between pi and pj . A triangulation of P is a collection of n 3 diagonals (i.e., chords connecting non-adjacent vertices) of P such that no two diagonals intersect (except possibly at their endpoints). Notice that a triangulation splits the polygons interior into n 2 disjoint triangles. The cost of a triangulation is the sum of the lengths of the diagonals in it. Give an efficient algorithm for finding the cost of a minimum cost triangulation. [Hint: For 1 i < j n, let the subproblem Cost(i, j) denote the minimum cost triangulation of the polygon spanned by the vertices pi , . . . , pj .]