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.

There is a set of $n$ points in the 2-dimensional plane. All x values and all y values are different. We want to draw the largest set of axis-parallel rectangles such that:

  • All rectangles are pairwise interior-disjoint.
  • Every rectangle has (at least) two points at opposite corners.

The number of possible rectangles is obviously related to the locations of the points. Here are two examples with $n=8$:

$n-1$ is probably the worst case (fewest possible rectangles), as we can always order the points according to their $x$ axis and draw a rectangle between point $i$ to point $i+1$.

MY QUESTION IS: What is the best case - i.e. the largest number of rectangles possible, as a function of $n$?

share|improve this question

2 Answers 2

up vote 0 down vote accepted

If you arrange your points on the grid $\mathbb{Z}^2$, and take the "even" points $X=\{(x,y)| x+y \text{ is even} \}$ to be your set of points, then every grid square of the form $[i,i +1]\times[j,j+1]$ is a legal rectangle. Now each rectangle has two even points and each even point touches four rectangles, so there are twice as many rectangles as points.

This is an infinite example, but if you consider the even points of a large enough grid then the ratio $\frac{\#rectangles}{\#points}$ will converge to 2.

Conversely, it isn't hard to show that a ratio of two is the best that is possible by using a common technique in combinatorics: we look at the set of pairs $$X = \{(\text{point, rect}) : \text{ point $\in$ rect } \}$$ We count $X$ in two different ways. Once by summing over points and once by summing over rectangles. $$ |X| = \sum_{ \text{point $x$}}{\#\text{rectangles containing $x$}} \leq 4 \cdot \#points . $$ On the other hand: $$ |X| = \sum_{\text{rect. $R$}}{\#\{\text{points $\in R$}\}} \geq 2 \cdot \#rects . $$

Putting these two inequalities together we get $\frac{\#rects}{\#points} \leq 2$.

share|improve this answer
    
This makes sense, but can you prove that $2n$ is indeed the maximum? –  Erel Segal Halevi Dec 28 '13 at 16:14
    
Thanks for the clarification. Indeed, since any point can belong to at most 4 different rectangles, and any rectangle needs at least 2 different points, the ratio must be at most 2. –  Erel Segal Halevi Dec 29 '13 at 14:11

The idea will be clear once you arrange $4$ points to get $4$ rectangles. Suppose the points are $(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)$. Then if $x_1<x_2<x_3<x_4$ and $y_3<y_1<y_4<y_2$ you get the maximum number of rectangles ($4$ in this case). Similarly arrange the rest of the points. See the figure for $n=8$.

enter image description here

We have to arrange the points in such a way that the number of such 4-point-configurations is maximized. So for $n$ points, we need to find the largest perfect square $\leq n$, let it be $c^2$. Then arrange $c^2$ points in a $c\times c$ array, such that the groups of closest 4 points always follow the above configuration. Then we put the rest $n-c^2$ points in such a way that the number of squares added is maximized.

For example say $n=12$. Then $c^2=9$, we first arrange $9$ points in the following manner: enter image description here

and then add $3$ more points:

enter image description here

Alternatively you can find the smallest perfect square $\geq n$, let it be $c^2$, then construct the $c\times c$ array as above and remove $c^2-n$ points from the border.

for example when $n=15$, $c^2=16$:

enter image description here

then remove one point:

enter image description here

share|improve this answer
    
Thanks! Can you prove that this is the maximum possible? –  Erel Segal Halevi Dec 28 '13 at 15:58
    
You can exhaust all cases and check that by adding two new points you can add at most 3 more rectangles. That is the justification behind this construction. –  Abishanka Saha Dec 28 '13 at 17:24
    
Well... it seems the construction by Zur Luria produces more rectangles: tora.us.fm//math/graphics/… –  Erel Segal Halevi Dec 28 '13 at 20:34
    
True that! I have been worng! The construction strategy is basically the same. I described the configuration of 4 closest points that would maximize the number of rectangles. We have to arrange the points in such a way that the number of such 4-point-configurations is maximized. So for $n$ points we need to express $n$ as $ab$ such that $a$ is the largest divisor of $n$, which is $\leq\sqrt{n}$. We then arrange the points in a $a\times b$ lattice, such that each each row of the lattice is constructed in the method described above. –  Abishanka Saha Dec 29 '13 at 5:09
    
This method can still be improvised, and I have edited my answer likewise. Please take a look. –  Abishanka Saha Dec 29 '13 at 5:24

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.