6
$\begingroup$

Not sure whether this question belongs here or math.stackexchange.

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 step, 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?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ As the problem is stated you could make a polygon of area as close to zero as you like which contains the given vertices. Are there some other constraints, like the vertices have to be lattice points or something? $\endgroup$
    – Noah Stein
    Commented Jan 4, 2015 at 15:05
  • $\begingroup$ @NoahStein: Well, it has to be a simple polygon (i.e no self-intersection). No other constraint $\endgroup$
    – fajrian
    Commented Jan 4, 2015 at 16:23
  • 2
    $\begingroup$ What is missing from your description is a requirement that all the vertices of the polygon must be among the given points. If the polygon can have vertices not in the given set, then one can easily make a star-shaped polygon with area $\epsilon$ for any $\epsilon > 0$. (I assume this is what Noah meant by his comment.) $\endgroup$
    – Joseph O'Rourke
    Commented Jan 4, 2015 at 17:52
  • $\begingroup$ @JosephO'Rourke: Oh, yes. That's true. Thanks for that! $\endgroup$
    – fajrian
    Commented Jan 4, 2015 at 18:55
  • $\begingroup$ @JosephO'Rourke: Yes, that is what I meant. Also, nice answer. $\endgroup$
    – Noah Stein
    Commented Jan 5, 2015 at 4:06

1 Answer 1

Reset to default
13
$\begingroup$

I assume you intend the problem in which the polygon's vertices must be exactly the given set of points. If so, then, Yes, the problem is NP-hard:

Fekete, Sándor P. "On simple polygonalizations with optimal area." Discrete & Computational Geometry 23.1 (2000): 73-110. (Journal link.)

          Fig1a

Approximation algorithms have been explored:

Taranilla, María Teresa, Edilma Olinda Gagliardi, and Gregorio Hernández Peñalver. "Approaching minimum area polygonization." (2011): 161-170. (Authors' link.)

The key search term for this problem is polygonization.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Actually the vertices can be inside the polygon. But I think it will be impossible to have a vertex inside polygon while minimizing the polygon area. So yes, those vertices must all be the polygon vertices. $\endgroup$
    – fajrian
    Commented Jan 4, 2015 at 16:24

You must log in to answer this question.

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