Minimum and Maximum number of triangulations of a polygon

Question

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.

Answer 1

1. Convex polygons (ones with all internal angles less than $180^\circ$) have minimal polygons equal to the number of vertices minus 2.

Note: While these are all regular (same lengths and angles) they don't have to be. (It was just easier to draw.)

2. Any concave corners increase the number of polygons required. Many kinds of polygons have maximal triangles. Easy to draw examples would be stars (but lots of convolutions of these basic shapes are possible).

3. This is a very broad question and whole books could be written about this as there are so many cases to cover. I'd recommend reading up on computer graphic triangulation and computer graphic primitives.

Answer 2

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.