# Area of an irregular, n-sided, non-intersecting (edges) polygon algorithm

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.

• What is the condition on the side lengths? – Tony Huynh Feb 11 '16 at 4:03
• You receive the vertices, so it depends on it. – Kolt Penny Feb 11 '16 at 4:08

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.
• OP doesn't use the word, "convex", so I'm not sure this is what's wanted. It may be one is required to have on the boundary all of the $n$ points given. – Gerry Myerson Feb 11 '16 at 4:54