Disjoint rectangles with points at their corners

Question

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

• here only n-1=7 rectangles are possible.
• here n+1=9 rectangles are possible.

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

Answer 1

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

Answer 2

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: