# Disjoint rectangles with points at their corners

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

-

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

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

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:

and then add $3$ more points:

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

then remove one point:

-
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