Skip to main content
a little tighter; deleted 1 characters in body
Source Link
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. And each of the four outermost rectangle edges cannot have any of its points covered by two rectangles. So if there are $n$ rectangles, there are at most $4n$$4n-4$ 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$$\binom{n}{2}\le 4n-4$, true only when $n\le 9$$n<9$. So this argument shows that one can't have tennine 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$.

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

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. And each of the four outermost rectangle edges cannot have any of its points covered by two rectangles. So if there are $n$ rectangles, there are at most $4n-4$ 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-4$, true only when $n<9$. So this argument shows that one can't have nine rectangles in the pattern you ask for.

added 349 characters in body
Source Link
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$.

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.

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

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