0
$\begingroup$

Not sure whether this question belongs here or mathoverflow.

You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be inside the polygon, but they must NOT be outside the polygon (and I think to get the minimum-area polygon, they must be the polygon vertices). The polygon can be concave.

I am thinking of using convex-hull algorithm as the first, and then from each edge of the convex-hull polygon, I "dig in" by removing an edge from the aforementioned polygon (let the edge connects vertex a and vertex b), and create 2 new edges (a-c and c-b) where c is a vertex which was previously located inside the polygon. And do it until there is no more edge remaining inside the polygon (i.e all vertices have become the polygon vertices). But I haven't got the "digging in" algo which is proven to minimize the polygon area.

As a side question, is this an NP-complete problem?

$\endgroup$
1
  • $\begingroup$ Cross-posted to MathOverflow: mathoverflow.net/q/192114 $\endgroup$
    – user856
    Commented Jan 5, 2015 at 11:34

1 Answer 1

Reset to default
0
$\begingroup$

The area of the polygon can become arbitrarily small. You could e.g. construct a spanning tree for your set of points, then thicken its edges by a tiny amount to obtain a polygon instead of a planar graph. The less you thicken, the less its area will be.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .