Complexity of existence of simple polygonalization with prescribed area? 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 &amp; Computational Geometry 23.1 (2000): 73-110
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.