A triangulation of a convex polygon results in a set of non-intersecting diagonals between non-adjacent vertices, which completely partition the interior of the convex hull of the polygon into triangles. The minimum weight triangulation (MWT) is the triangulation having the minimum total edge length among all possible triangulation.



For example, the following are the two triangulations of the same convex pentagon. The triangulation on the left has a cost of 8 + 2√2 + 2√5 (approximately 15.30), the one on the right has a cost of 4 + 2√2 + 4√5 (approximately 15.77).[2]
Minimum-weight triangulation of a convex polygon

A polygon triangulation of minimal weight may be constructed using a dynamic programming algorithm that considers all possible diagonals that lie within the polygon, recursively finds the optimal triangulation on each side of the diagonal, and picks the diagonal leading to the minimum total weight.
Suppose the vertices are numbered consecutively around the boundary of the polygon. If MWT(i,j) is the weight of the minimum-weight triangulation of the polygon for an edge ij, the optimal triangulation may be recursively obtained by choosing the triangle ikj that leads to the minimum value for MWT(i,j), and recursively searching MWT(i,k) and MWT(j,k). This can be recursively defined as:

The above recurrence relation can be implemented as follows in C++, Java, and Python. The implementation assumes that the vertices are given in either clockwise or counterclockwise order.

C++

Download   Run Code

Output:

The weight of optimal triangulation is 15.3006

Java

Download   Run Code

Output:

The weight of optimal triangulation is 15.30056307974577

Python

Download   Run Code

Output:

The weight of optimal triangulation is 15.30056307974577

Download   Run Code
Output:

The weight of optimal triangulation is 15.3006

Download   Run Code
Output:

The weight of optimal triangulation is 15.30056307974577

Download   Run Code
Output:

The weight of optimal triangulation is 15.30056307974577

The time complexity of the above solution is exponential. On drawing a recursion tree, we can easily see that each subproblem gets repeated several times. The problem satisfies both optimal substructure and overlapping subproblems properties of dynamic programming, so the subproblem solutions can be derived using memoization or in a bottom-up manner.
Following is the dynamic programming solution in C, Java, and Python, that iteratively build up a table of values T[i][j] to prevent redundant calculations of the same value.

C++

Download   Run Code

Output:

The weight of optimal triangulation is 15.3006

Java

Download   Run Code

Output:

The weight of optimal triangulation is 15.30056307974577

Python

Download   Run Code

Output:

The weight of optimal triangulation is 15.30056307974577

Download   Run Code
Output:

The weight of optimal triangulation is 15.3006

Download   Run Code
Output:

The weight of optimal triangulation is 15.30056307974577

Download   Run Code
Output:

The weight of optimal triangulation is 15.30056307974577

The time complexity of the above dynamic programming solution is O(n3) and requires O(n2) extra space.

source