3
$\begingroup$

This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is a closed chain of straight line segments that does not cross itself).

I am interested in the complexity of this problem:

Input: Set $S$ of $N$ points on integer 2D grid and a rational number $A$

Question: Is there a polygonalization that has enclosed area $A$?

Is this problem still NP-complete?

The area $A$ is given as an integer (represented in unary)

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

$\endgroup$
1
2
$\begingroup$

The answer to your question is already contained in Fekete's paper. In Section 3, Fekete shows that the following problem GRID-EMPTY is NP-complete:

Problem: GRID-EMPTY
Instance: a set $S$ of $n$ grid points in the plane
Question: Is there a simple polygon on this vertex set $S$ that does not contain any other grid points on its boundary or in its interior?

By Pick's theorem, every simple polygon with grid vertices that has $b$ grid points on its boundary and $i$ grid points in its interior has area $(b+2i-2)/2$.

For the scenario in GRID-EMPTY, the smallest possible area is $(n-2)/2$, and this area can be reached if and only if the answer to the GRID-EMPTY instance is YES.
Hence, you simple have to set $A:=(n-2)/2$ in Fekete's reduction and get NP-completeness of your question.

$\endgroup$

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.