6
$\begingroup$

There are $n$ rectangles packed in a square; all of them are axes-parallel. You are allowed to partition the square into a grid of cells, with $1$ or more rows and $1$ or more columns. You score a point for each cell that contains at least one whole rectangle.

What is the maximum score $s(n)$ you can get, for the worst-case initial arrangement of $n$ rectangles?

Here are two examples for $n=4$. Here:

enter image description here

your score is 4 (the maximum), since there are 4 cells (out of 6) that contain a whole rectangle. However, here:

enter image description here

your score is only 3, since there are only 3 cells and each of them contains a whole rectangle (a cell with more than one rectangle is worth only one point). Moreover, here:

enter image description here

In any grid containing more than 2 cells (e.g. $1\times 3$ or $3\times 1$ or $2\times 2$), at least 2 rectangles are cut, so at most 2 cells contain whole rectangles. This example proves that $s(4)\leq 2$.

On the other hand, it is obvious that you can always score at least $2$ by just taking any two rectangles and creating a $2\times 1$ grid. Therefore $s(4)=s(3)=s(2)=2$.

The above example can be generalized by partitioning each rectangle into $n/4$ rectangles, such that each horizontal line cuts at least $n/4$ vertical rectangles and vice-versa. It gives an upper bound of $s(n) \leq \lceil n/2 \rceil$.

Is it always possible to score at least $\lceil n/2 \rceil$? If not, what is the maximum possible score in the worst case?

$\endgroup$
  • $\begingroup$ Are the rectangles required to be congruent, or can the square be packed with rectangles of mixed sizes? Must the grid cells be square? Are the rectangle width and heights required to be multiples of the cell size? $\endgroup$ – Paul Sinclair May 24 at 17:06
  • 1
    $\begingroup$ @PaulSinclair The original rectangles need not be congruent - they can be of arbitrary sizes. Similarly, the cells in the grid need not be congruent - each row/column may have any height/width. There are no constraints on the widths and heights of the rectangles or the cells - they just need to be positive. $\endgroup$ – Erel Segal-Halevi May 24 at 18:52
  • $\begingroup$ I'm not understanding your intent. If the cells are smaller than the rectangles, then obviously, your score is always $0$, regardless of the arrangements. If the entire square is a cell, the score is $n$. $\endgroup$ – Paul Sinclair May 24 at 19:03
  • $\begingroup$ @PaulSinclair I added some more examples and explanations - I hope it is clearer now. $\endgroup$ – Erel Segal-Halevi May 24 at 20:00
4
+50
$\begingroup$

I’m amazed how you can devise new problems in so well-studied domain as plain combinatorial geometry.

My first attack of the problem brought the following results.

Proposition 1. If $n$ is not least than Ramsey number $R(m,m)$ then $s(n)\ge m$.

Proof. Consider a graph whose vertices are the packed rectangles. Let any two vertices of the graph are adjacent by a red edge, if they can be separated by a vertical line and by a blue edge, if they can be separated by a horizontal line. Since any two packed rectangles can be separated either by a vertical or a horizontal line, each edge of the graph is either red or blue. Since $n\ge R(m,m)$, there are a (vertical or horizontal) direction and a set $S$ of $m$ packed rectangles such that any two distinct rectangles of $S$ can be separated by a line parallel to the direction. Then the segment, which are orthogonal projections of rectangles of $S$ parallel to the direction, have pairwise disjoint interiors. Thus the lines parallel to the direction and erected from the endpoints of the segment provided a grid with score $m$. $\square$

Since $R(3,3)=6$, Proposition 1 implies that $s(6)=3$.

Unfortunately, Proposition 1 provides weak asymptotic lower bounds for $s(n)$, because asymptotic bounds for $R(m,m)$ are exponential.

We can improve them by the following

Proposition 2. For any natural $n$, we have $s(n)\ge \sqrt{n}$.

Proof. Define a binary relation $<$ on the set $H$ of the horizontal projections of the packed rectangles, putting $I<I’$ if the right endpoint of the segment $I\in H$ lies at the left of (or coincides with) the left endpoint of the segment $I’\in H$. It is easy to check that $(P,\le)$ is a partially ordered set. Diworth’s theorem implies that $H$ has either a chain of size at least $\sqrt{n}$ or an antichain $A$ of that size. In the former case similarly to the end of the proof of Proposition 1 we obtain a grid with score at least $\sqrt{n}$. In the latter case interiors of each two segments of $A$ intersect. Helly’s theorem implies that all interiors of the segments of $A$ have a common point. It follows that interiors of vertical projections of the rectangles horizontally projected to the segments of $A$ are pairwise disjoint, and we can proceed similarly to the former case. $\square$

Proposition 2 implies that $s(5)=3$.

Lemma 3. For each natural $a$, $b$, and $c$, we have $s(ab+2c)\le \max\{ab,a+c,b+c\}$.

Proof. The claim is provided by a packing consisting of $2c$ rectangles attached to a rectangle $a\times b$ partitioned into $ab$ squares with. See below an example for $a=3$, $b=2$, and $c=2$. $\square$

enter image description here

Proposition 4. For each $a\ge 2$ we have $s(3a^2-2a)\le a^2$.

Proof. In Lemma 3 put $a=b$ and $c=a^2-a$. $\square$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks. It seems that these bounds hold even if we limit the grid to all-horizontal or all-vertical lines, right? In this case, there is a simple upper bound of $\lceil\sqrt{n}\rceil$ where the arrangement is a grid of $\lceil\sqrt{n}\rceil$ by $\lceil\sqrt{n}\rceil$ squares. $\endgroup$ – Erel Segal-Halevi Jun 5 at 9:46
  • 1
    $\begingroup$ Proposition 4 implies that $n/2$ is not always attainable - there is an asymptotic upper bound of $n/3$, right? $\endgroup$ – Erel Segal-Halevi Jun 5 at 13:39
  • $\begingroup$ @ErelSegal-Halevi You are right in both cases. Proposition 4 implies that $s(n)\le \left(\lceil \sqrt{n/3}\rceil+1\right)^2$ for each $n$. $\endgroup$ – Alex Ravsky Jun 5 at 15:54

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.