Grid Avoiding Polygon(Grid-Empty): Given $n$ grid points in the plane. Is there a simple polygon on this vertex set that does not contain any other grid points on its boundary or in its interior.
Grid-Full Polygonalization(Grid-Full): Given $n$ grid points $V$ in the plane. Is there a simple polygon on this vertex set that contains as many other additional grid points as well as possible. Consider the convex hull of $V$ Let $h_i(V)$ denote the number of points that are strictly inside the convex hull but not the n points. Let $h_b(V)$ be the number of grid points that are on the boundary of the convex hull but not the n points. So the problem is there a polygon $P$ such that the number of grid points it contains is all of the $n+h_i(V) + h_b(V)$ points?
I was thinking about the reduction Grid-Empty $\leq_P$ Grid-Full
The below paper does not give a reduction explicitly. What they do is they reduce Hamiltonian circuit to Grid-Empty by constructing a specific instance of Grid-Empty such that two points are the rightmost of all the other points. Now from this specific instance they add 4 points which are like a bounding square for the vertex set and now they get the iff relation 
by finding the complement from the bounding square. I get that to preserve this complement relation we need to constrict such that the edges $t_1p_2 , p_2p_4, p_4p_3, p_3p_1, p_1t_2$ have to be edges of any solution of the resulting instance of Grid-Full.
How could we give a polynomial time reduction without making assumptions for Grid-Empty. How could we construct from a general instance of Grid-Empty problem to prove $Grid-Empty \leq_P Grid-Full$.
https://en.wikipedia.org/wiki/Polynomial-time_reduction
Fekete, Sándor P. "On simple polygonalizations with optimal area." Discrete & Computational Geometry 23.1 (2000): 73-110. (Journal link.)
Assume wlog that $|V|\ge 3$.
Let $v\in V$ be on the boundary $\partial \mathcal H$ of the convex hull $\mathcal H$ of $V$. Assume that $w\in V$ is the (counter-clockwise) next neighbour of $v$ in a solution of $\operatorname{GridEmpty}(V)$ (needing to try all $w$ adds a factor of $O(n)$ to our method). By applying an orientation-preserving grid automorphism, we may assume wlog. that $v=(0,0)$ and $w=(-1,0)$. Let $x_\min, x_\max, y_\min,y_\max$ be the minima/maximal $x$/$y$ coordinates of points $\in V$ (determined in $O(n)$).
Assume for the moment that
Now we add points $p:=(x,1)$, $q:=(x+1,1)$, and $s:=(x+1,2)$ to $V$, where $x\gg 0$. I claim that $\operatorname{GridEmpty}(V\cup\{p,q,s\})$ has a solution, and that every such solution looks like $\ldots vqspw\ldots$ (i.e., the points $v,q,s,p,w$ occur in direct succession and in this order along the counterclockwise polygon making up the solution).
Definition. An obstacle is a grid point that is $\notin \mathcal H$ and $\notin\{p,q,s\}$.
By Pieck's formula, a grid triangle with $n_b$ grid points on its boundary (including the vertices) and $n_i$ interior grid points has area $A=n_i+\frac12n_b-1<n_i+n_b$. Hence conversely if $A\ge |\mathcal H|+3$, then the grid triangle contains at least one obstacle.
For $a,b\in V$, the (signed) area of triangle $abp$ is polynomial in $x$ of degree $\le 1$. We ignore the only case when it is in fact constant, namely the case $\{a,b\}=\{v,w\}$. For all other cases, $a,b$ determine some $x_{a,b}$ with $|abp|\ge |\mathcal H|+3$ and $|abs|\ge|\mathcal H|+3$ for all $x\ge x_{a,b}$. (Automatically, also $|abq|\ge |\mathcal H|+3$). Likewise, for $a\in V$, the (signed) area of triangle $aps$ is a degree one polynomial in $x$, so that $a$ determines some $x_a$ with $|aps|\ge |\mathcal H|+3$ for all $x\ge x_a$. Note that we do not need to compute $|\mathcal H|$ explicitely and may use $(x_\max-x_\min+1)(y_\max-y_\min+1)$ instead. Finally, there is some $x_0$ such that $x\ge x_0$ guarantees that $s$ is below the line through $w$ and $(x_\max,1)$.
Thus (at $O(n^2)$ cost), we let $$ x=\biggl\lceil\max\Bigl\{x_0, \max\bigl\{\,x_{a,b}\bigm | a,b\in V, a\ne b, \{a,b\}\ne\{v,w\}\,\bigr\}, \max\bigl\{\,x_{a}\bigm | a\in V\,\bigr\}\Bigr\}\biggr\rceil$$ and thereby guarantee the existence of obstacles as needed in the proof below:
The last point follows from the
Observation 1. If $abcd$ is a simple quadrangle, then at least one of the triangles $abc$, $bcd$ is fully contained in the quadrangle $abcd$. (Specifically, if $a$ is not further than $d$ from $bc$, then we can take $abc$, and otherwise $bcd$).
Proposition 1. Replacing the edge $vw$ of our given solution to $\operatorname{GridEmpty}(V)$ with $vqspw$ produces a solution of $\operatorname{GridEmpty}(V\cup\{p,q,s\})$.
Proof. Indeed, the added parallelogram and added triangle cannot contribute any new gridpoints apart from $p,q,s$. And the resulting polygon is still simple because any edge that crosses any of the new edges must in fact cross the two edges $vq$ and $pw$, which contradicts $v\in\partial \mathcal H$. $\square$
Proposition 2. Every solution of $\operatorname{GridEmpty}(V\cup\{p,q,s\})$ has the form $\ldots vqspw\ldots$.
Proof. Assume otherwise.
Let $a$ be the predecessor, $b$ the successor of $s$ in a polygon solving $\operatorname{GridEmpty}(V\cup \{p,q,s\}$. If $a,b\in V$, then triangle $abs$ contains an obstacle that cannot be "repaired" by the rest of the polygon.
If $b=q$, our polygon is wrongly oriented / describes the unbounded region:
If $b=p$ and $a\ne q$, the same happens:
We conclude that $a=q$. If $b\ne p$, then one of the following situations happens, and in both cases we find a quadrangle with an obstacle. Even though the quadrangle need not be completely inside our polygon, the obstacle cannot be "repaired" by other edges living in $\mathcal H$.
Thus we msut have $\ldots cqspd\ldots$ for some $c,d\in V$. Unless $\{c,d\}=\{v,w\}$, we find an obstacle in the highlighted quadrangle (namely, in one of the triangles $cdp$ or $cdq$).
Finally, $\{c,d\}=\{v,w\}$ implies $c=v$ and $d=w$ as otherwise the polygon is not simple. $\square$
Now add the following points: $t_1=(x,y_\max+1)$. $t_2=(x_\min-1,y_\max+2)$, $t_3=(x_\min-2,y_\min-2)$, and $t_4=(x,y_\min-1)$. By replacing the edge $qs$ of our $\operatorname{GridEmpty}(V\cup\{p,q,s\})$ solution above with $qt_4t_3t_2t_1s$ (and reversing orientation), we obtain a $\operatorname{GridFull}(V\cup\{p,q,s,t_1,t_2,t_3,t_4\})$ solution.
, consider an arbitrary $\operatorname{GridFull}(V\cup\{p,q,s,t_1,t_2,t_3,t_4\})$ solution. We must have edge $st_1$ in order to cover point $(x,y_\max)$. We must have edge $t_1t_2$ in order to cover point $(x-1,y_\max+1)$. Similarly, we must have edges $t_2t_3$, $t_3t_4$, and $t_3s$.
In other words, our $\operatorname{GridFull}(V\cup\{p,q,s,t_1,t_2,t_3,t_4\})$ solution looks like $\ldots st_1t_2t_3t_4q\ldots $. Replace $st_1t_2t_3t_4q$ with $sq$ and flip orientation to obtain a $\operatorname{GridEmpty}(V\cup\{p,q,s\})$ solution. As seen above, this gives us a $\operatorname{GridEmpty}(V)$ (which is incidentally guaranteed to have $vw$ as edge).
Now what if we cannot guarantee the weird condition that $y=0$ is the only horizontal line containing more than one point of$ V$?
In short, add a single "far away" point $p$ as above. Then $vp$ and $wp$ will not be parallel to any possible line segment $ab$ with $a,b\in V$. Also, $p$ will be on the boundary of the extended convex hull. Now let $pv$ play the role of $vw$, and the desired condition holds. Note that in general we cannot reconstruct the original $\operatorname{GridEmpty}(V)$ from a $\operatorname{GridEmpty}(V\cup\{p\})$ solution. A uniqueness result similar to proposition 2 fails in general because there may exists other adjacent points $v',w'\in V$ with $v'w'\|vw$, and therefore a $\operatorname{GridEmpty}(V\cup\{p\})$ solution might look like $\ldots v'pw'\ldots$ instead. However, by the next extension of the point set, we know that $pv$ is an edge and as $v$ is on the convex hull boundary, only $w$ can be the other point.