Generating all triangulations of simple polygon

Question

Having simple polygon how can we generate all triangulations of this polygon? How can it be done ? What would be the approach ?

I didn't find any paper explaining it, only about planar triconnected graphs.

In fact we can present polygon as planar graph, but not triconnected.

Thanks for any math hints and basic ideas.

Chris

Answer 1

Each diagonal of the polygon divides it into two subpolygons. Recursively find all triangulations of these two polygons. Vary the diagonal and you'll get all triangulations of the original polygon.