4
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – user856
    Commented Mar 6, 2012 at 21:54

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .