Home > Combinatorics, Geometry, Problem Solving > Rectangles in the plane

## Rectangles in the plane

We consider a finite family of rectangles in plane, having edges parallel with the coordinate axes such that for any pair of rectangles there exists a vertical line, or a horizontal one which intersects both rectangles. Prove that there exists a vertical line and a horizontal one such that any of the given rectangles intersects at least one of them.

Proof: If no pair of rectangles can be joined by a vertical line then every two rectangles can be joined by a horizontal line. By Helly’s theorem (one dimensional case), the projections of the rectangles on the $Oy$ axis have a common point, which means that there exists a horizontal line joining all the rectangles. This line paired with any vertical line solve our problem.

Next, suppose that we have at least two rectangles which can be joined by a vertical line. Denote $\mathcal{R}=\{R_i\}$ a family of rectangles such that any two of them can be joined by a vertical line. Considering the projections of the rectangles in $\mathcal{R}$ on the $Ox$ axis and applying Helly’s theorem again, we see that the intersection of the projection is a non-void and compact interval $K$. Denote by $\mathcal{H}$ the family formed by the rest of rectangles. If $\mathcal{H}=\emptyset$, then we are done. Else we split $\mathcal{H}$ in two sets $\mathcal{H}_1,\mathcal{H}_2$ as being the rectangles whose projections on $Ox$ are on the left of $K$, and respectively on the right. Since the intersection yielding $K$ is finite, there exists on rectangle $R_2$ whose right vertical side projects on the right frontier of $K$. This means that all the rectangles in $\mathcal{H}_2$ (if there are some) cannot be joined verticaly with $R_2$, and therefore are all joined horizontally with $R_2$. We do the same thing to find a similar rectangle $R_1$ which intersects horizontally every rectangle in $\mathcal{H}_1$.

To be continued…