# Generating all triangulations of simple polygon

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

-
hey, yeah, seems like a good approach. Could you give approximate complexity of this algorithm? Because for me it's $O(n/2 + 2* n/4 + 4*n/8....)$ ? Because we divide first polygon with $n/2$ diagonal each subpolygon with $n/4$ diagonals and so on Is that true? Or am i wrong? –  Chris Nov 7 '11 at 16:59