Complexity of existence of simple polygonalization with prescribed area?

Question

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

Answer 1

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.