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…

 

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: