Minimum-weight triangulation of a convex polygon
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 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:
= 0, otherwise
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 58 |
#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 2D plane double dist(Point p1, Point p2) { // The distance between vertices `(x1, y1)` and `(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(vector<Point> const &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 triangulation is the length of the perimeter of a triangle double weight = dist(vertices[i], vertices[j]) + dist(vertices[j], vertices[k]) + dist(vertices[k], vertices[i]); // choose 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 the optimal triangulation is " << MWT(vertices, 0, vertices.size() - 1) << endl; return 0; } |
Output:
The weight of the 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 |
// A 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)` and `(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 triangulation is the length of the perimeter of a triangle double w = vertices[i].dist(vertices[j]) + vertices[j].dist(vertices[k]) + vertices[k].dist(vertices[i]); // choose vertex `k` that leads to the minimum total weight cost = Double.min(cost, w + 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 the optimal triangulation is " + MWT(vertices, 0, vertices.length - 1)); } } |
Output:
The weight of the 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 49 50 51 |
import sys from math import sqrt # A class 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)` and `(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 triangulation is the length of the perimeter of a triangle weight = dist(vertices[i], vertices[j]) +\ dist(vertices[j], vertices[k]) +\ dist(vertices[k], vertices[i]) # choose 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 the optimal triangulation is', MWT(vertices, 0, len(vertices) - 1)) |
Output:
The weight of the 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 72 73 |
#include <iostream> #include <algorithm> #include <vector> #include <limits> #include <cstring> #include <cmath> 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 2D plane double dist(Point p1, Point p2) { // The distance between vertices `(x1, y1)` and `(x2, y2)` is // `v((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(vector<Point> const &vertices) { // get the number of vertices in the 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]; memset(T, 0.0, sizeof T); // 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 triangulation is the length of its perimeter double weight = dist(vertices[i], vertices[j]) + dist(vertices[j], vertices[k]) + dist(vertices[k], vertices[i]); // choose 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 the optimal triangulation is " << MWT(vertices) << endl; return 0; } |
Output:
The weight of the 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 74 75 76 77 78 |
// A 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)` and `(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 the 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 triangulation is the length of its perimeter double weight = vertices[i].dist(vertices[j]) + vertices[j].dist(vertices[k]) + vertices[k].dist(vertices[i]); // choose 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 the optimal triangulation is " + MWT(vertices)); } } |
Output:
The weight of the 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 49 50 |
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)` and `(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 the 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 triangulation is the length of its perimeter weight = dist(vertices[i], vertices[j]) + \ dist(vertices[j], vertices[k]) + \ dist(vertices[k], vertices[i]) # choose 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 the optimal triangulation is', MWT(vertices)) |
Output:
The weight of the optimal triangulation is 15.30056307974577
The time complexity of the above dynamic programming solution is O(n3) and requires O(n2) extra space, where n is the total number of vertices.
References:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)