# 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.

• Look at Catalan numbers, for example: math.umn.edu/~reiner/Classes/Catalan.pdf Oct 15 '16 at 18:04
• It seems that you can find (partial) answers here. Oct 5 '18 at 5:42
• @mathlove Thanks! How can I end the bounty? Oct 5 '18 at 6:00
• @Arman Malekzadeh: See here. Oct 5 '18 at 6:04

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.

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