Let P be a convex polygon, a triangulation of P is an addition of diagonals connecting the vertices of P so that each interior face is a triangle. The weight of a triangulation is the sum of the...

Let
P
be a convex polygon, a

triangulation

of
P
is an addition of diagonals

connecting the vertices of
P
so that each interior face is a triangle.

The

weight

of a triangulation is the sum of the lengths of the diagonals.

Assuming that we can compute lengths and add and compare them in constant

time, give an efficient algorithm for computing a minimum-weight

triangulation of
P.