Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Can we place $n$ axis-parallel rectangles on 2D plane (e.g. four sides of each rectangle must be parallel to either x-axis or y-axis) such that for every pair of rectangles, there is a region that is contained in the intersection of the two rectangles but NOT contained in any other $n-2$ rectangles.

For $n = 1, 2, 3,$ and $4,$ it is a rather trivial task - you can draw some rectangles to find such arrangements. (for $n=1,2,3,4$, here's the arrangements: http://www.freeimagehosting.net/image.php?5260dfe888.png ). However, this does not seem to work for $n=5$ or higher.

Can you prove or disprove that you can place $n>=5$ axis-parallel rectangles to have the above property?

share|improve this question

3 Answers 3

I wrote a simple program to check the 5!3 (1,728,000) arrangements for N=5.

There were no solutions. The closest was 9 out of 10 pairs (below).

alt text

share|improve this answer
    
Hi, it is good to know that it's not possible to construct such a configuration even when n = 5 (assuming that your program is correct). However, it would be nicer if there is a proof that disproves the statement (but not by trying every possible arrangement). Thanks for sharing this! –  ltdtl Jul 26 '10 at 14:44

By the one-dimensional Helly theorem, if all pairs of rectangles intersect, there must be a vertical line $x=x_0$ and a horizontal line $y=y_0$ that crosses all the rectangles.

Now suppose that rectangles $A$ and $B$ intersect in a rectangle $R$ that is partially uncovered. If $p$ is an uncovered point of $R$, then moving $p$ farther from the lines $x=x_0$ and $y=y_0$ cannot lead to any other points that are covered by any third rectangle, so we can assume without loss of generality that $p$ is one of the four corners of $R$. Then $p$ has the property that it is covered by two rectangles, and that along the boundary edges of $A$ and $B$ that it lies on any other point that is farther from the lines $x=x_0$ and $y=y_0$ is not covered by two rectangles.

Each rectangle could potentially have eight extreme points covered by two rectangles like $p$: two on each of its four edges. But each partially uncovered intersection uses up two of those potentialities. And each of the four outermost rectangle edges cannot have any of its points covered by two rectangles. So if there are $n$ rectangles, there are at most $4n-4$ different partially uncovered intersections.

In order for all pairs of rectangles to have a partially uncovered intersection, we would need $\binom{n}{2}\le 4n-4$, true only when $n<9$. So this argument shows that one can't have nine rectangles in the pattern you ask for.

share|improve this answer

Notice that you are trying to draw Venn diagrams using only rectangles.

http://en.wikipedia.org/wiki/Venn_diagram

Check: http://www.combinatorics.org/Surveys/ds5/VennOpenEJC.html

It states that it is an open problem whether it is always possible to construct a Venn diagram using congruent curves, and particularly, if it is possible to draw a 6-Venn diagram in which each curve is a rectangle.

share|improve this answer
    
First off, thanks for the link to a list of related open problems. That's very helpful. I see that drawing Venn diagrams using rectangles is very related to my question. However, does having every pair of rectangles to have an intersected region that is not contained in any of the rest rectangles necessarily imply that there should be 2^n regions? That is, I am not interested in how many regions that are formed by n rectangles as long as each pair has its intersected region not touched by other rectangles (these two might be equivalent, although it is not obvious to me). –  ltdtl Jul 25 '10 at 13:50
1  
The conditions on a Venn diagram are substantially stronger than what the question asks for. –  JBL Jul 25 '10 at 13:53
    
You are right; my mistake. –  Nick Jul 26 '10 at 6:42

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.