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.
2
-
$\begingroup$ What is the condition on the side lengths? $\endgroup$– Tony HuynhFeb 11, 2016 at 4:03
-
$\begingroup$ You receive the vertices, so it depends on it. $\endgroup$– Kolt PennyFeb 11, 2016 at 4:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Feb 11, 2016 at 4:25
-
$\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$ Feb 11, 2016 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$ Feb 11, 2016 at 4:58