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

8 points, 7 squares

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

3 points, 2 squares

  • 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$: LEFT: it is not possible to draw a square at the bottom and the parallel square at the left, because they intersect. RIGHT: Therefore, we can draw only $k-1$ squares.

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.

  • 4
    Yeah, we remember. Alas, no ideas yet, but by all means keep bumping it once a year :-). – fedja Nov 1 '13 at 12:45
  • Is it conceivable that there is always a set of paradises that connect waterpoints only pairwise, so that the resulting graph (interpreting paradises as edges) is connected? – Johan Wästlund Jan 28 '14 at 16:11
  • @JohanWästlund I didn't understand the question. In order to have a connected graph with $n$ vertices (waterpoints), we need at least $n-1$ edges (paradises)? – Erel Segal-Halevi Jan 29 '14 at 14:58
  • 1
    What happens when you replace squares by rectangles (or equivalently by parallelograms)? Your upper bound $n-1$ for the worst case remains valid but your counterexample no longer works! – Roland Bacher Jan 29 '14 at 17:17
  • 1
    @RolandBacher it is always possible to draw $n-1$ rectangles, for example, by scanning the points from left to right, and drawing a rectangle between $p_i$ to $p_{i+1}$ for $i=1,...,(n-1)$ – Erel Segal-Halevi Jan 29 '14 at 18:08

After a lot of playing around, I found this counter-example with $n=6$ points and only 4 squares. This link alone is not a sufficient proof because there might be a bug in my function that calculates the maximum disjoint set. So here is a formal description of the arrangement, and an attempt to prove that indeed no more than 4 squares are possible:

enter image description here

First, consider only the 4 points near the x axis (blue). We can consider only squares between adjacent points, because squares between non-adjacent points can be shrinked to touch only adjacent points. Between each of the 3 pairs of adjacent points, there are 2 options to draw a square: either above the x axis, or below it. There is a small overlap between these 2 squares, so only one square per pair is possible:

enter image description here

Second, consdier the point at the top of the y axis (red). Any square that uses this point must have a side-length of at least 6 in order to approach the x axis. Any such square necessarily blocks at least two of the cyan squares above the x axis. Additionally, the leftmost square is slightly larger than 6 and thus also blocks the middle cyan square below the x axis. The two extreme options are plotted below in magenta:

enter image description here

The case for the point at the bottom of the y axis (red) is the same.

All in all, a maximum set of disjoint squares can be drawn in only the following ways (ordered in an increasing order fo the number of magenta squares):

  1. One magenta square at the top-left(bottom-right), and 3 cyan squares below(above) the x-axis.
  2. Two magenta squares at the top(bottom), and 2 cyan squares below(above) the x-axis. Or, one magenta square at the top-left(right), one magenta square at the bottom-right(left), one cyan square at the left(right) below the x axis, and one cyan square at the right(left) above the x axis.
  3. Two magenta squares at the top(bottom), one magenta square at the bottom-left(top-right), and one cyan square at the right(left) below(above) the x axis.
  4. Two magenta squares at the top and two at the bottom.

In all ways, there are only 4 squares. Hence $p(6)\leq 4$.


This construction can be duplicated and translated a long distance to the left and bottom (for example). For every duplication, we get more 6 points and more 4 squares, but an additional square can be added between two adjacent duplicates. This gives a bound of: $p(6k)\leq 5k-1$ for every integer $k$, i.e. $p(n)/n \lesssim 5/6$.

A further improvement can probably be achieved by creating 6 copies of the construction, arranged in just the same way as the original construction. This can be continued recursively like a fractal, and gives $p(6^k)\leq 4\cdot(6^{k-1}+...+1) = 4\cdot\frac{6^k}{5}$ for every integer $k$, i.e., $p(n)/n \lesssim 4/5$.


This upper bound is still far away from the lower bound of $p(n)/n \gtrsim 1/6$...

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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