0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Nov 7 '11 at 21:42
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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