I need to generate an irregular, n-sided polygon of non-intersecting edges (n= 200, for example) with the smallest area possible. The position of the vertex is random and I've tried designing a couple of algorithms with no satisfying result. Is there something out there with this specifications or a way of designing it? I have OpenGL if it helps.
Given a set of $n$ points in the plane, the problem of finding a minimum area convex $k$-gon among the points was considered by Eppstein, Overmars, Rote, and Woeginger in this paper. They give an algorithm that runs in time $O(kn^3)$.
As Gerry Myerson mentions, there is also the variant where we do not require the $k$-gon to be convex. Both these problems can be solved in time $O(kn^k)$ by checking all $k$-tuples of points. However, this paper by Eppstein claims that no faster algorithm is known (see the Introduction) for the non-convex version.