Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Working on the 2D plane, I'm looking for an elegant proof of the fact that if four regions $A$, $B$, $C$, $D$ delimited by axis-parallel rectangles are such that:

  • $A$ intersects $B$,
  • $B$ intersects $C$,
  • $C$ intersects $D$,
  • $D$ intersects $A$,
  • $A$ does not intersect $C$, and $B$ does not intersect $D$

(in other words, the intersection graph of these four rectangles is a cycle) then these four rectangles delimit another rectangular region of points that do not belong to any of $A$, $B$, $C$, or $D$.

enter image description here

It looks obvious on such a picture. But surely there must be some elegant way to prove this fact.

My current approach would be to define each region $R=([R_{x},R_{x'}], [R_{y}, R_{y'}])$ as pair of intervals (the projection on each axis). Then justify that $[A_{x},A_{x'}]\cap[C_{x},C_{x'}]\ne\emptyset \iff [A_{y},A_{y'}]\cap[C_{y},C_{y'}]=\emptyset$ (otherwise $A$ would intersect $C$ or $B$ would intersect $D$), likewise for $B$ and $D$. Then by symmetry fix an order on $A$, $B$, $C$, $D$, so it looks like in the picture with $A_{y'}< C_{y}$ and $B_{x'}<D_{x}$. And finally note that rectangular the region $((B_{x'},D_{x}),(A_{y'},C_{y}))$ does not intersect $A$, $B$, $C$, nor $D$. This looks very clumsy to me.

Maybe there is a Jordan-curve-like theorem I could use?

share|improve this question
1  
I think your approach can be distilled into the following. If $B$ does not intersect $D$, then there is some interval of $x$- or $y$-coordinates that lies strictly between them. Similarly for $A$ and $C$, and it has to be the other axis because otherwise $A$ and $C$ could not intersect both $B$ and $D$. The product of the intervals therefore intersects none of the rectangles. That seems elegant enough to me. –  Rahul Mar 6 '12 at 21:54

1 Answer 1

up vote 0 down vote accepted

We have to factor out the obvious symmetries.

(1) The relations $[A_x, A_{x'}]\cap [C_x, C_{x'}]\ne\emptyset$ and $[A_y, A_{y'}]\cap [C_y, C_{y'}]\ne\emptyset$ cannot both hold since then $A$ and $C$ would intersect.

(2) Therefore we may assume $A_{y'}<C_y$. Then $B_y<A_{y'}<C_y<B_{y'}$, and similarly $D_y<A_{y'}<C_y<D_{y'}$. It follows that $[B_y,B_{y'}]\cap[D_y,D_{y'}]\ne\emptyset$, and using (1), applied to $B$ and $D$, we conclude that $[B_x,B_{x'}]\cap[D_x,D_{x'}]=\emptyset$. Therefore we may assume $B_{x'}<D_x$.

(3) Now $B_{x'}>A_x$ (or $B$ would not intersect $A$), and similarly $B_{x'}>C_x$, $D_x<A_{x'}$, $D_x<C_{x'}$. It follows that $[B_{x'},D_x]\times[A_{y'},C_y]$ is the region you are looking for.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.