UPDATE: I created a simple web-application, that allows the user to move waterpoints around, then automatically calculates a maximum set of interior-disjoint squares between the points (the algorithm is exponential so it works only up to about $n=11$ points).
There are $n$ waterpoints in an infinite desert. Assume each waterpoint is a point in $\Bbb R^2$, and the x and y values of the points are all different.
Define a paradise as an axis-aligned square which touches at least two waterpoints.
Define $p(n)$ as the maximum number of interior-disjoint paradises in the worst possible arrangement of $n$ waterpoints. What is $p(n)$?
SOME SIMPLE CASES:
If the waterpoints are on a diagonal (e.g. $\{(i,i)|1\leq i\leq n\}$), then there can be only a single paradise between each pair of adjacent waterpoints, for a total of $n-1$. Hence: $p(n) \leq n-1$:
For $n \leq 5$, it can be checked that $p(n) = n-1$:
- For $n=1, 2$ this is obvious.
- For $n=3$, put 2 paradises in the following way. Order the waterpoints in an increasing order of their x value ($x_1 < x_2 < x_3$). Cut the plane to two half-planes using a vertical line through $x_2$. The western half-plane contains two waterpoints $x_1$ and $x_2$, so you can put a paradise there. The same is true for the eastern half-plane. Hence: $p(3)=2$.
- For $n=4$, Cut the plane to two half-planes using a vertical line through $x_2$. Put a single paradise in the western half-plane through $x_1$ and $x_2$. In the eastern half-plane, order the 3 paradises vertically in an increasing order of their y values and cut to two quarter-planes using a horiznotal line through $y_2$. Each quarter-plane contains 2 waterpoints so you can have a single square in each. Hence: $p(4)=3$.
- For $n=5$, Cut the plane to two half-planes using a vertical line through $x_3$. Cut the two half-planes to two quarter-planes each using horizontal lines. Each quarter-plane contains 2 waterpoints (some of them on the boundary) so you can put a single paradise in each quarter-plane. Hence: $p(5)=4$.
This cutting scheme doesn't work anymore when $n>5$, because if we end up with 3 waterpoints in a quarterplane, it might be impossible to have 2 paradises.
On the other hand, in all cases that I checked, I always managed to find $n-1$ paradises.
So the question is: is it always possible to have $n-1$ paradises, for every $n$? If so, how? If no, what is the minimum?
PREVIOUS WORK:
Several months ago I published a similar question in math.SE, with a major difference: instead of an infinite desert, there was a finite (square) cake (i.e. all points and squares should be within a large predefined square).
With the help of an answer from prof. Boris Bukh, I managed to prove an upper bound of: $$p(n) \leq \lceil{n \over 2}\rceil - 1$$ The proof was by constructing a set of $n=2k$ points, that are organized such that it is not possible to put more than $p=k-1$ squares. The following figures illustrate the construction for $k=6$:
Later I also proved a lower bound of: $$ p(n) \geq {(n+2) \over 6} \ \ \ \ \ [n \geq 2]$$ The proof was by describing a recursive algorithm that, given a square with $n$ points, divides the square to 4 smaller squares, and puts paradises separately in each of them.
Now I am trying to adapt these results to the infinite desert case.
The upper bound construction crucially relies on the assumption that the cake is bounded in at least two adjacent directions. It can work in a quarter-plane, but not in an unbounded desert ($\Bbb R^2$).
(In a half-plane, a similar construction leads to an upper bound of $p(n) \leq \lceil{2(n-1) \over 3}\rceil$).
The lower bound algorithm will obviously work in an infinite desert, however, after only a single iteration, we will have 4 quarter-planes, and thus the lower bound will not be much better than in the bounded-cake case.
