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
:All vertices of the polygon except first belong to parabola.
Each triangulation of
n-gon
hasn - 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.