2
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Feb 11 '16 at 4:54
  • 1
    $\begingroup$ @GerryMyerson That's true. The wording of the question was a bit vague, so I took my best guess at what it meant. I guess we will have to wait until the OP clarifies. $\endgroup$ – Tony Huynh Feb 11 '16 at 4:58

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.