Minimum and Maximum number of triangulations of a polygon
Triangulation of a simple polygon $P$ is a decomposition of $P$ into triangles by a maximal set of non-intersecting diagonals. We also know that triangulation of a polygon is not neccessarily unique. The question (taken from Computational Geometry in C by J. Rourke):
Which polygons have the fewest number of distinct triangulations? Can polygons have unique triangulations? Which polygons have the largest number of distinct triangulations?
Note: I've already answered the second part by drawing a convex 4-gon with only 1 possible diagonal. The problem is the other two parts.
Number of triangulations of convex n-gon
is the (n − 2)
nd Catalan number. This is maximum possible number of triangulations.
Let's consider following n-gon
:
(n, 0), (0, 0), (1, 1), (2, 4), ..., (i, i^2), ..., (n - 2, (n - 2)^2).
All vertices of the polygon except first belong to parabola.
Each triangulation of n-gon
has n - 3
diagonals.
The only convex vertices are first, second and last. Any diagonal with both ends on the parabola is invalid (lies outside of polygon). So we have only n - 3
valid diagonals connecting vertices: (1, 3), (1, 4), ..., (1, n - 1)
. These diagonals make up one and only one triangulation.