# proving that four axis-parallel rectangles whose intersection graph is a cycle delimit another rectangle

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

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?

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