<p>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: </p>

<blockquote>
  <p><strong>Problem:</strong> GRID-EMPTY<br>
  <strong>Instance:</strong> a set <span class="math-container">$S$</span> of <span class="math-container">$n$</span> grid points in the plane<br>
  <strong>Question:</strong> Is there a simple polygon on this vertex set <span class="math-container">$S$</span> that does not contain any other grid points on its boundary or in its interior?</p>
</blockquote>

<p>By Pick's theorem, every simple polygon with grid vertices that has <span class="math-container">$b$</span> grid points on its boundary and <span class="math-container">$i$</span> grid points in its interior has area <span class="math-container">$(b+2i-2)/2$</span>.</p>

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

CC BY-SA 4.0
2019-08-01T14:47:02.713Z
2019-08-01T14:47:02.713Z
Gamow
<p>This is a followup on my previous <a href="https://mathoverflow.net/questions/328229/what-is-known-about-this-tsp-variant">question</a>. 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).</p>

<p>I am interested in the complexity of this problem:</p>

<p>Input: Set <span class="math-container">$S$</span> of <span class="math-container">$N$</span> points on integer 2D grid and a rational number <span class="math-container">$A$</span> </p>

<p>Question: Is there a polygonalization that has enclosed area <span class="math-container">$A$</span>?</p>

<blockquote>
  <p>Is this problem still NP-complete? </p>
</blockquote>

<p>The area <span class="math-container">$A$</span> is given as an integer (represented in unary)</p>

<p>Fekete, Sándor P. <a href="http://link.springer.com/article/10.1007%2FPL00009492#page-1" rel="nofollow noreferrer">"On simple polygonalizations with optimal area."</a> <em>Discrete &amp; Computational Geometry</em> <strong>23</strong>.1 (2000): 73-110</p>

CC BY-SA 4.0
2019-08-01T12:47:22.933Z
This was posted on Mathoverflow without getting an answer: https://mathoverflow.net/questions/335417/complexity-of-existence-of-simple-polygonalization-with-prescribed-area
Mohammad Al-Turkistany
<cc.complexity-theory><np-hardness><cg.comp-geom><polygon>
Complexity of existence of simple polygonalization with prescribed area?
Mohammad Al-Turkistany
# Complexity of existence of simple polygonalization with prescribed area?

(Asked by: username_0 on 2019-08-01)

This is a followup on my previous [question](https://mathoverflow.net/questions/328229/what-is-known-about-this-tsp-variant). 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."](http://link.springer.com/article/10.1007%2FPL00009492#page-1) *Discrete & Computational Geometry* **23**.1 (2000): 73-110

**Tags:** cc.complexity-theory, np-hardness, cg.comp-geom, polygon
> **Comments:**
> **username_0**: This was posted on Mathoverflow without getting an answer: https://mathoverflow.net/questions/335417/complexity-of-existence-of-simple-polygonalization-with-prescribed-area  

---

## 1 answers

### Answer by username_1 on 2019-08-01. Score: 2 | Accepted answer

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.


---

