[Math] Minimum and Maximum number of triangulations of a polygon

computational geometrytriangulation

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.

Best Answer

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.

Related Question