Skip to main content
1 of 3
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.

David Eppstein
  • 18.6k
  • 2
  • 55
  • 127