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