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]
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++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <iostream>
#include <limits>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
// Data structure to store a point in the Euclidean plane
struct Point {
int x, y;
};
// Utility function to return the distance between two vertices in a 2-dimensional plane
double dist(Point p1, Point p2)
{
// The distance between vertices `(x1, y1)` & `(x2, y2)` is
// `√((x2 − x1) ^ 2 + (y2 − y1) ^ 2)`
return sqrt((p1.x – p2.x) * (p1.x – p2.x) + (p1.y – p2.y) * (p1.y – p2.y));
}
// Function to calculate the weight of optimal triangulation of a convex polygon
// represented by a given set of vertices `vertices[i..j]`
double MWT(const vector<Point> &vertices, int i, int j)
{
// If the polygon has less than 3 vertices, triangulation is not possible
if (j < i + 2) {
return 0;
}
// keep track of the total weight of the minimum weight triangulation of `MWT(i,j)`
double cost = numeric_limits<double>::max();
// consider all possible triangles `ikj` within the polygon
for (int k = i + 1; k <= j – 1; k++)
{
// The weight of a triangulation is the length of perimeter of the triangle
double weight = dist(vertices[i], vertices[j]) +
dist(vertices[j], vertices[k]) +
dist(vertices[k], vertices[i]);
// choose the vertex `k` that leads to the minimum total weight
cost = min(cost, weight + MWT(vertices, i, k) + MWT(vertices, k, j));
}
return cost;
}
int main()
{
// vertices are given in clockwise order
vector<Point> vertices = { {0, 0}, {2, 0}, {2, 1}, {1, 2}, {0, 1} };
cout << “The weight of optimal triangulation is “
<< MWT(vertices, 0, vertices.size() – 1) << endl;
return 0;
}
|
Output:
The weight of optimal triangulation is 15.3006
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
// Class to store a point in the Euclidean plane
class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
// Function to return the distance between two vertices in a 2-dimensional plane
public double dist(Point p)
{
// The distance between vertices `(x1, y1)` & `(x2, y2)` is
// `√((x2 − x1) ^ 2 + (y2 − y1) ^ 2)`
return Math.sqrt((this.x – p.x) * (this.x – p.x) +
(this.y – p.y) * (this.y – p.y));
}
}
class Main {
// Function to calculate the weight of optimal triangulation of a convex polygon
// represented by a given set of vertices `vertices[i..j]`
public static double MWT(Point[] vertices, int i, int j)
{
// If the polygon has less than 3 vertices, triangulation is not possible
if (j < i + 2) {
return 0;
}
// keep track of the total weight of the minimum weight triangulation of `MWT(i,j)`
double cost = Double.MAX_VALUE;
// consider all possible triangles `ikj` within the polygon
for (int k = i + 1; k <= j – 1; k++)
{
// The weight of a triangulation is the length of perimeter of the triangle
double weight = vertices[i].dist(vertices[j]) +
vertices[j].dist(vertices[k]) +
vertices[k].dist(vertices[i]);
// choose the vertex `k` that leads to the minimum total weight
cost = Double.min(cost, weight + MWT(vertices, i, k) + MWT(vertices, k, j));
}
return cost;
}
public static void main(String[] args)
{
// vertices are given in clockwise order
Point[] vertices = {
new Point(0, 0), new Point(2, 0), new Point(2, 1),
new Point(1, 2), new Point(0, 1)
};
System.out.println(“The weight of optimal triangulation is “
+ MWT(vertices, 0, vertices.length – 1));
}
}
|
Output:
The weight of optimal triangulation is 15.30056307974577
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
import sys
from math import sqrt
# Data structure to store a point in the Euclidean plane
class Point:
def __init__(self, x=None, y=None):
self.x = x
self.y = y
# Utility function to return the distance between two vertices in a 2-dimensional plane
def dist(p1, p2):
# The distance between vertices `(x1, y1)` & `(x2, y2)` is
# `√((x2 − x1) ^ 2 + (y2 − y1) ^ 2)`
return sqrt((p1.x – p2.x) * (p1.x – p2.x) + (p1.y – p2.y) * (p1.y – p2.y))
# Function to calculate the weight of optimal triangulation of a convex polygon
# represented by a given set of vertices `vertices[i..j]`
def MWT(vertices, i, j):
# If the polygon has less than 3 vertices, triangulation is not possible
if j < i + 2:
return 0
# keep track of the total weight of the minimum weight triangulation of `MWT(i,j)`
cost = sys.maxsize
# consider all possible triangles `ikj` within the polygon
for k in range(i + 1, j):
# The weight of a triangulation is the length of perimeter of the triangle
weight = dist(vertices[i], vertices[j]) +
dist(vertices[j], vertices[k]) +
dist(vertices[k], vertices[i])
# choose the vertex `k` that leads to the minimum total weight
cost = min(cost, weight + MWT(vertices, i, k) + MWT(vertices, k, j))
return cost
if __name__ == ‘__main__’:
# vertices are given in clockwise order
vertices = [Point(0, 0), Point(2, 0), Point(2, 1), Point(1, 2), Point(0, 1)]
print(“The weight of optimal triangulation is”, MWT(vertices, 0, len(vertices) – 1))
|
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++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include <iostream>
#include <limits>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
// Data structure to store a point in the Euclidean plane
struct Point {
int x, y;
};
// Utility function to return the distance between two vertices in a 2-dimensional plane
double dist(Point p1, Point p2)
{
// The distance between vertices `(x1, y1)` & `(x2, y2)` is
// `√((x2 − x1) ^ 2 + (y2 − y1) ^ 2)`
return sqrt((p1.x – p2.x) * (p1.x – p2.x) + (p1.y – p2.y) * (p1.y – p2.y));
}
// Function to calculate the weight of optimal triangulation of a convex polygon
// represented by a given set of vertices
double MWT(const vector<Point> &vertices)
{
// get the number of vertices in polygon
int n = vertices.size();
// create a table for storing the solutions to subproblems
// `T[i][j]` stores the weight of the minimum-weight triangulation
// of the polygon below edge `ij`
double T[n][n] = { };
// fill the table diagonally using the recurrence relation
for (int diagonal = 0; diagonal < n; diagonal++)
{
for (int i = 0, j = diagonal; j < n; i++, j++)
{
// If the polygon has less than 3 vertices, triangulation is not possible
if (j < i + 2) {
continue;
}
T[i][j] = numeric_limits<double>::max();
// consider all possible triangles `ikj` within the polygon
for (int k = i + 1; k <= j – 1; k++)
{
// The weight of a triangulation is the length its perimeter
double weight = dist(vertices[i], vertices[j]) +
dist(vertices[j], vertices[k]) +
dist(vertices[k], vertices[i]);
// choose the vertex `k` that leads to the minimum total weight
T[i][j] = min(T[i][j], weight + T[i][k] + T[k][j]);
}
}
}
// the top-rightmost element in the table stores the result
return T[0][n – 1];
}
int main()
{
// vertices are given in clockwise order
vector<Point> vertices = { {0, 0}, {2, 0}, {2, 1}, {1, 2}, {0, 1} };
cout << “The weight of optimal triangulation is “ << MWT(vertices) << endl;
return 0;
}
|
Output:
The weight of optimal triangulation is 15.3006
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
// Class to store a point in the Euclidean plane
class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
// Function to return the distance between two vertices in a 2-dimensional plane
public double dist(Point p) {
// The distance between vertices `(x1, y1)` & `(x2, y2)` is
// `√((x2 − x1) ^ 2 + (y2 − y1) ^ 2)`
return Math.sqrt((this.x – p.x) * (this.x – p.x) +
(this.y – p.y) * (this.y – p.y));
}
}
class Main {
// Function to calculate the weight of optimal triangulation of a convex polygon
// represented by a given set of vertices
public static double MWT(Point[] vertices)
{
// get the number of vertices in polygon
int n = vertices.length;
// create a table for storing the solutions to subproblems
// `T[i][j]` stores the weight of the minimum-weight triangulation
// of the polygon below edge `ij`
double[][] T = new double[n][n];
// fill the table diagonally using the recurrence relation
for (int diagonal = 0; diagonal < n; diagonal++)
{
for (int i = 0, j = diagonal; j < n; i++, j++)
{
// If the polygon has less than 3 vertices, triangulation is not possible
if (j < i + 2) {
continue;
}
T[i][j] = Double.MAX_VALUE;
// consider all possible triangles `ikj` within the polygon
for (int k = i + 1; k <= j – 1; k++)
{
// The weight of a triangulation is the length its perimeter
double weight = vertices[i].dist(vertices[j]) +
vertices[j].dist(vertices[k]) +
vertices[k].dist(vertices[i]);
// choose the vertex `k` that leads to the minimum total weight
T[i][j] = Double.min(T[i][j], weight + T[i][k] + T[k][j]);
}
}
}
// the top-rightmost element in the table stores the result
return T[0][n – 1];
}
public static void main(String[] args)
{
// vertices are given in clockwise order
Point[] vertices = {
new Point(0, 0), new Point(2, 0), new Point(2, 1),
new Point(1, 2), new Point(0, 1)
};
System.out.println(“The weight of optimal triangulation is “ + MWT(vertices));
}
}
|
Output:
The weight of optimal triangulation is 15.30056307974577
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
import sys
from math import sqrt
# Utility function to return the distance between two vertices in a 2-dimensional plane
def dist(x, y):
# The distance between vertices `(x1, y1)` & `(x2, y2)` is
# `√((x2 − x1) ^ 2 + (y2 − y1) ^ 2)`
return sqrt((x[0] – y[0]) * (x[0] – y[0]) + (x[1] – y[1]) * (x[1] – y[1]))
# Function to calculate the weight of optimal triangulation of a convex polygon
# represented by a given set of vertices
def MWT(vertices):
# get the number of vertices in a polygon
n = len(vertices)
# create a table for storing the solutions to subproblems
# `T[i][j]` stores the weight of the minimum-weight triangulation
# of the polygon below edge `ij`
T = [[0.0] * n for _ in range(n)]
# fill the table diagonally using the recurrence relation
for diagonal in range(n):
i = 0
for j in range(diagonal, n):
# If the polygon has less than 3 vertices, triangulation is not possible
if j >= i + 2:
T[i][j] = sys.maxsize
# consider all possible triangles `ikj` within the polygon
for k in range(i + 1, j):
# The weight of a triangulation is the length its perimeter
weight = dist(vertices[i], vertices[j]) +
dist(vertices[j], vertices[k]) +
dist(vertices[k], vertices[i])
# choose the vertex `k` that leads to the minimum total weight
T[i][j] = min(T[i][j], weight + T[i][k] + T[k][j])
i += 1
# the top-rightmost element in the table stores the result
return T[0][–1]
if __name__ == ‘__main__’:
# vertices are given in clockwise order
vertices = [(0, 0), (2, 0), (2, 1), (1, 2), (0, 1)]
print(“The weight of optimal triangulation is”, MWT(vertices))
|
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.