Area covered by convex polygon centered at vertices of the unit square

200 Views Asked by At

Let $U$ be a convex symmetric polygon. Put a copy of $U$ at each vertex of the unit square. Let $t$ be the smallest positive real number such that $\mathcal{U} = \cup_{\mathbf{a}\in \{0,1\}^2} tU + \mathbf{a}$ covers the unit square. See figure below.

Now if I let $\mathcal{U}' = \cup_{\mathbf{a}\in \{0,1\}^2} \frac{t}{2}U + \mathbf{a}$ (as shown in the rightmost picture) is it true that $\mathcal{U}'$ covers $\leq \frac{1}{2}$ of the area of the unit square?

Convexity is crucial here since there are counter-examples for non-convex polygons. I would still like to try to solve this problem, so I will accept answers which contain relevant theorems or resources (papers, textbooks, lecture notes).

2

There are 2 best solutions below

3
On BEST ANSWER

Consider the following counterexample. Let $U$ be a long strip extending to infinity in both directions (you can think of these as long skewed rectangles if you like). In the figure below, the red, green, blue, and purple polygons represent the relevant portion of the strip scaled by $\frac{t}{2}$ and placed at $(0,0), (1,0), (0,1)$, and $(1,1)$ respectively.

Figure 1.

The darkened portions are where the strips intersect with the unit square. The light yellow parts are the portions of the unit square not covered by any polygon. By rearranging the colored regions we see that $\mathcal{U} = \cup_{a\in \{0,1\}^2} a + \frac{t}{2}U$ covers $\frac{2}{3}$ of the area. Thus the area covered by $\mathcal{U}$ is greater than $\frac{1}{2}$.

The natural extension to this problem is to see if there is any constant $k < 1$ such that the area covered by $\mathcal{U}$ is less than $k$.

3
On

Taking into account the comments, if your (bounded) convex polygon is given by $$U=\left\{ x\in\mathbb R^2\mid \left\|Ax\right\|_\infty\le 1 \right\},\ [A]_{m\times 2} $$ you don't necessarily have the property you want, see the (bad) illustration below.

Counter-example

I didn't bother actually computing it out, but visually the polygon $\frac t2U$ (at the origin) alone covers more than half of the unit square. This works because the constraints $\|Ax\|_\infty\le 1$ only guarantee that the origin will lie inside the polygon, but it can still be arbitrarily close to the boundary. The dilation by factor $t$ then very slowly enlarges the polygon in the directions that are "too close" to the origin, while the directions that are "far away" will already have covered most of the unit square.

To prevent the above, you most likely have to enforce that the center/origin is not too far away from the center of mass of the polygon. Even then, I have a feeling that if the polygon is too skewed, it may still not work. Either way, if you don't have additional properties beside convexity, the property is false.


Edit: Looked it into it a little bit more, couldn't come up with a counter-example when the center is the center of mass, so maybe that constraint would work...