How can I give a polygon with exactly a given number of triangulations?

250 Views Asked by At

I'm studying for a computational geometry exam and I found this question on one of the past years' exams - "give a 5-sided polygon in R^2 with exactly 2 triangulations". I've found lots of information on the number of triangles in a polygon's triangulation and the number of sides in a triangulation, but nothing about the number of triangulations a polygon can have (except for convex polygons, which this clearly can't be since a 5-sided convex polygon has 5 triangulations - the 3rd Catalan number, right?). How do I solve something like this?

1

There are 1 best solutions below

2
On BEST ANSWER

A triangulation of a 5gon is determined by one special vertex, at which two diagonals end. So our 5gon shall have to such vertices. Can these vertices be neighbours, say $A$ and $B$? No, because with diagonal $AC$, $AD$, and $BD$, $BE$, we also have the two diagonals ending at $D$ and hence a third triangulation. Hence the two special vertices are not adjacent, so wlog they are $A$ and $C$, and we have diagonals $AC$, $AD$, and $CE$. Thus $B$ must be blocked from "seeing" $D$ or $E$.

enter image description here