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.

– Community Bot
Dec 20 '21 at 19:45
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.)

1. 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). 1. 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.
• My question was about number of ways one can triangulate a polygon. Your answer is about number of triangles made by a triangulation... Oct 9 '16 at 8:49
• Oh right. I misread it. I don't think there is any short answer to the question you've asked. I'll leave this here for now and delete if you want. Oct 9 '16 at 11:21