Skip to main content
2 of 3
added 349 characters in body
David Eppstein
  • 18.6k
  • 2
  • 55
  • 127

By the one-dimensional Helly theorem, if all pairs of rectangles intersect, there must be a vertical line $x=x_0$ and a horizontal line $y=y_0$ that crosses all the rectangles.

Now suppose that rectangles $A$ and $B$ intersect in a rectangle $R$ that is partially uncovered. If $p$ is an uncovered point of $R$, then moving $p$ farther from the lines $x=x_0$ and $y=y_0$ cannot lead to any other points that are covered by any third rectangle, so we can assume without loss of generality that $p$ is one of the four corners of $R$. Then $p$ has the property that it is covered by two rectangles, and that along the boundary edges of $A$ and $B$ that it lies on any other point that is farther from the lines $x=x_0$ and $y=y_0$ is not covered by two rectangles.

Each rectangle could potentially have eight extreme points covered by two rectangles like $p$: two on each of its four edges. But each partially uncovered intersection uses up two of those potentialities. So if there are $n$ rectangles, there are at most $4n$ different partially uncovered intersections.

In order for all pairs of rectangles to have a partially uncovered intersection, we would need $\binom{n}{2}\le 4n$, true only when $n\le 9$. So this argument shows that one can't have ten rectangles in the pattern you ask for.

I'm pretty sure it can be strengthened to show that nine rectangles also don't work: in each of the four quadrants surrounding the point $(x_0,y_0)$ the graph having the input rectangles as vertices and having an edge for every uncovered intersection must be a tree, so there can really only be $4(n-1)$ uncovered intersections rather than $4n$.

David Eppstein
  • 18.6k
  • 2
  • 55
  • 127