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 Grid-Full solves Grid-Empty 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$.


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



  • $\begingroup$ I do not understand your description of the Grid-Full problem. Isn't the answer trivially "yes"? - There are finitely many simple polygons on the given vertex set and at least one of these "contains as many other [additional] grid points as [well as] possible" $\endgroup$ Dec 4 '19 at 18:57
  • 1
    $\begingroup$ @HagenvonEitzen I have edited to make it clear. Does this make sense? Grid-Full solution contains all the grid points possible in the convex hull $\endgroup$
    – T.Harish
    Dec 4 '19 at 19:07

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

The $x$-axis is the only horizontal line containing more than one point $\in V$.

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:

  • Every triangle $abs$ with $a,b\in V$ contains an obstacle.
  • Every triangle $abp$ with $a,b\in V$ contains an obstacle, except when $\{a,b\}=\{v,w\}$.
  • Every triangle $aps$ with $a\in V$ contains an obstacle.
  • Every simple quadrangle $apsb$ with $a,b\in V$ contains an obstacle.

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. enter image description here

If $b=q$, our polygon is wrongly oriented / describes the unbounded region:

enter image description here

If $b=p$ and $a\ne q$, the same happens:

enter image description here

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$.

enter image description here enter image description here

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$).

enter image description here

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$.

enter image description here

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.


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.