2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ You say $U$ is a convex "symmetric" polygon, but what kind of symmetry do you want? Central symmetry, symmetry wrt to the X and Y-axis, something else? $\endgroup$
    – N.Bach
    Jan 16 '18 at 14:56
  • $\begingroup$ $U$ should be symmetric with respect to some line through its center. The symmetry is really here to establish the center to that I can put the center at each of the vertices of the unit square. $\endgroup$ Jan 16 '18 at 16:21
  • $\begingroup$ I'm a little sad, I think I had a proof when $U$ admits symmetry wrt to both the X and Y axes. So basically you don't want symmetry, but just a "center". I think it'd be better to just say that $U$ has an arbitrary center. Maybe you want to constrain it so that the center is inside $U$, or maybe define the center as the "barycenter" (not sure that's the word in English) of the vertices. If your center has stronger properties than that, it would really help if you can state those properties though. On a side note, I think regular polygons have a naturally well-defined "center" for this problem. $\endgroup$
    – N.Bach
    Jan 16 '18 at 17:14
  • 1
    $\begingroup$ Yep, regular polygons are just the kind of shapes that I want, but I also want to admit more skewed shapes. If it helps to make it more formal, I can define $U$ as $\{\mathbf{x} \in \mathbb{R}^2: \parallel A\mathbf{x} \parallel_{\infty} \leq 1\}$ where $[A]_{m \times 2}$ represents a system of $m$ linear constraints (with a non-empty feasible region) and $\parallel \cdot \parallel_{\infty}$ is the infinity norm. $U$ is then the convex polygon cut out by the constraints and $(0,0)$ is the center. $\endgroup$ Jan 16 '18 at 18:11
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ @N.Bach what do you think? $\endgroup$ Jan 25 '18 at 17:23
  • $\begingroup$ My bad, I didn't check on this question in a while, and you mentioning someone doesn't seem to work unless I've already commented on the answer... Based on your figure, I agree with the counter-example, though I find a different value for the area covered by the half-scaled rectangles. $\endgroup$
    – N.Bach
    Jan 31 '18 at 23:59
  • $\begingroup$ @N.Bach my bad, I didn't realize that that was how the comments worked. I agree there are probably better cases (less area covered by polytopes) but I think $\frac{2}{3}$ is an upper bound in two-dimensions. For higher dimensions I am not so sure... $\endgroup$ Feb 1 '18 at 14:18
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Hum... yeah, $\parallel A \mathbf{x} \parallel_{\infty}$ should force the centers to be at the centers of mass since each constraint (row $\mathbf{a}_i$ of $A$) represents two parallel lines $\mathbf{a}_i\cdot \mathbf{x} \leq 1$ and $\mathbf{a}_i\cdot \mathbf{x} \geq -1$. Anyways thanks for coming up with the "pseudo-counterexample" (and adding the nice illustrations)... I think this might still need more time. $\endgroup$ Jan 18 '18 at 0:46
  • $\begingroup$ @XinYuanLi My bad, I kinda forgot about that... but that changes a lot of things, since your polygon is always symmetric wrt to its center then. I'll have another look later. $\endgroup$
    – N.Bach
    Jan 18 '18 at 1:15
  • $\begingroup$ If only there were some property of convex polygons we could use... all I could think of is: "a convex polygon is the intersection of finitely many half-planes". I tried considering the intersection of each half-plane which composed the polygon with the unit square separately, but to no avail. $\endgroup$ Jan 18 '18 at 2:00

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.