Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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|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? –  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

Your Answer

 
discard

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.