2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Your link is broken. $\endgroup$
    – jeq
    Aug 12, 2017 at 1:49

3 Answers 3

4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – ltdtl
    Jul 26, 2010 at 14:44
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – ltdtl
    Jul 25, 2010 at 13:50
  • 1
    $\begingroup$ The conditions on a Venn diagram are substantially stronger than what the question asks for. $\endgroup$
    – JBL
    Jul 25, 2010 at 13:53
  • $\begingroup$ You are right; my mistake. $\endgroup$
    – Nick
    Jul 26, 2010 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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