Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
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? – Spinach 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 – Spinach 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. – Spinach Nov 7 '11 at 20:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.