How many whole rectangles can you catch in a grid?

Question

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:

your score is 4 (the maximum), since there are 4 cells (out of 6) that contain a whole rectangle. However, 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:

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?

NOTE: This question is related, but it considers a single cut rather than a grid.

Answer 1

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

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$

Answer 2

Proposition 5. For each natural $k\ge 4$, $s(k^2)\le k^2/4+k$.

Proof. Consider the following configuration of $k^2$ squares of size $a$ contained in a big square.

Let the catching grid consists of $h$ horizontal and $v$ vertical lines, so it catches at most $(h+1)(v+1)$ squares. Removing empty grid cells, we can assume that the distance between any two parallel grid lines it at most $a$ and $h,v\le k$. This provides all squares crossed by parallel grid lines are distinct. It is easy to check that each grid line crosses at least $k-1$ squares, so the grid crosses at least $h(k-1)+v(k-1)-hv$ squares ($hv$ is subtracted because of the double count), and so it catches at most $k^2-(k-1)(h+v)+hv$ squares. Put $h+v=2x\le 2k$. By the inequality between arithmetic and geometric means, $hv\le x^2$. So the grid cathes at most $\min\{x^2+2x+1, k^2-2(k-1)x+x^2\}$ squares. The following cases are possible:

• If $0\le x\le (k-1)/2$ then $x^2+2x+1\le (k^2+2k+1)/4$.
• If $k/2\le x\le k-1$ then $k^2-2(k-1)x+x^2\le k^2-2(k-1)(k/2)+(k/2)^2=k^2/4+k$.
• If $x=k-1/2$ then $k^2-2(k-1)x+x^2=2k-3/4$.
• If $x=k$ then $k^2-2(k-1)x+x^2=2k$. $\square$

Corollary 6. For each natural $n\ge 16$, $s(n)\le n/4+3\sqrt{n-1}/2+1$.

Proof. Pick the smallest $k$ such that $k^2\ge n$. Then $(k-1)^2\le n-1$ and $s(n)\le k^2/4+k\le 4+3\sqrt{n-1}/2+1.$ $\square$.

Proposition 7. When the input rectangles are all unit squares, $s(n)\geq n/4$.

Proof. Represent the squares by their bottom-left coordinates, $(x_i,y_i)$ for $i\in[n]$. Partition the squares into four groups:

1. $\lfloor x_i \rfloor$ is odd and $\lfloor y_i \rfloor$ is odd;
2. $\lfloor x_i \rfloor$ is odd and $\lfloor y_i \rfloor$ is even;
3. $\lfloor x_i \rfloor$ is even and $\lfloor y_i \rfloor$ is odd;
4. $\lfloor x_i \rfloor$ is even and $\lfloor y_i \rfloor$ is even.

Pick the largest group; it contains at least $n/4$ squares. Suppose w.l.o.g. that it is group 1. Then cut at $x=1, 3, 5, ...$ and $y = 1, 3, 5, ...$; the cuts do not harm any square of group 1.

Currently, the best lower bound for arbitrary rectangles is $s(n)\geq \sqrt{n}$. I conjecture that there should be a linear lower bound similar to $n/4$, but so far could not prove it.

EDIT: In the pattern below there are 40 squares, and it seems that the maximum score is 8, which implies an asymptotic upper bound $s(n)\leq n/5$ (not sure how to verify this):