# Polynomial time reduction from Min area polygon to max area polygon

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

https://mathoverflow.net/questions/192114/given-a-set-of-2d-vertices-how-to-create-a-minimum-area-polygon-which-contains/192115#192115

• 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" Dec 4 '19 at 18:57
• @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 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. 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.

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.