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.

Given simple polygon we have to find maximum area of smallest triangle in all possible triangulations.

I was trying to solve it by generating all possible triangulations, but for complex polygon it turned out to have number of triangulations equal to catalan(n).

Number of verticles is very small, but too big for factorial complexity.

Are there any other propeteries of triangulations and given above maximum "smallest" triangle?

Chris

share|improve this question

2 Answers 2

You can do a binary search for this maximum area. Say, you have a number S and you want to check whether the answer on your problem is at least S. That means that you want to check whether there exists a triangulation that consists only of triangles with area at least S. You can do this by a standard dynamic programming approach for minimum weight triangulation (see, for example, here).

share|improve this answer
    
Thanks for answer. Under your link there's approach for convex polygon, but i can have non convex one. Would it work also for non-convex? –  Chris Nov 7 '11 at 21:42

I don't know how flexible you are on your optimization criterion, but the constrained Delaunay triangulation is well-studied, has attractive properties, can be computed quickly, and high-quality software is available. It will not necessarily maximize the area of the smallest triangle, but it does avoid thin triangles as much as possible (as does the Delaunay triangulation). If you are interested, check out Jonathan Shewchuck's work on CDTs.

share|improve this answer

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.