# 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

-

## 1 Answer

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.

-
 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 The actual complexity depends on the polygon I guess because the number of diagonals varies. For convex polygons, which have as many diagonals as possible, the number of triangulations is huge, see Catalan number. – lhf Nov 7 '11 at 17:34 ouch okay, because i'm trying to find maximum value of smallest triangle over all triangulations in given simple polygon. So i see i have to work on another method than generating all triangulations. Do you have any idea how to solve it quite fastly? Thanks for answers – Chris Nov 7 '11 at 18:08 @Chris, perhaps you should ask a separate question now that you have accepted my answer? – lhf Nov 7 '11 at 19:14 Yes, you are right, i'll do it. – Chris Nov 7 '11 at 20:03