Largest rectangle not touching any rock in a square field

You want to build a rectangular house with a maximal area. You are offered a square field of area 1, on which you plan to build the house. The problem is, there are $n$ rocks scattered in unknown locations throughout the field. The rocks are unmovable, and you cannot build on rocks. What is the largest area of a rectangle that you can build, in the worst case?

Formally: let $S_n$ be a set of $n$ points in the unit square. Define $\textrm{MaxArea}(S_n)$ as the maximum area of an axis-parallel rectangle in the unit square that does not contain, in its interior, any point in $S$. Define:

$$\textrm{MinMaxArea}(n) = \inf_{S_n} (\textrm{MaxArea}(S_n))$$

where the infimum is on all possible sets $S_n$ of $n$ points. What are good bounds on $\textrm{MinMaxArea}(n)$?

EXAMPLE: In the picture below, the unit square is scaled to a 100-by-100 square. There are $n=100$ rocks. Apparently, the largest possible rectangle that does not contain any rocks in its interior is a rectangle such as ABCD, whose area is $.06\times .58$, which is approximately $\frac{1}{4\sqrt{n}}$, so:

$$\textrm{MinMaxArea}(n) \leq \frac{1}{4\sqrt{n}}$$

Is there another arrangement of rocks in which the largest rectangle is smaller?

Solution 1:

I dealt with this problem long ago. Here are my results. They are still unpublished, so I support an idea to write a joint paper.

Solution 2:

Let me shorten MaxArea($S_n$) to $M(S_n)$ for convenience, and let $M(n) = \inf_{S_n} M(S_n)$ be MinMaxArea (this is overloading the notation, but I hope it won't be confusing).

Then, $M(S_n) \le D(S_n)$, where $D(S_n)$ is the classical discrepancy function:

$$ D(S_n) = \sup_R \left|\frac{|S_n \cap R|}{n} - \mathrm{area}(R) \right|, $$ where the supremum is over axis-parallel rectangles in $[0,1]^2$. There are quite a few constructions of $n$-point sets $S_n$ for which $D(S_n) = O(\log(n)/n)$. One example is $$ S_n = \left\{ \left(\frac{i}{n}, i\sqrt{2} \bmod 1\right) \right\}_{i = 0}^{n-1}. $$ Another is the van der Corput set. This shows that $M(n) = O(\log(n)/n)$.

As far as lower bounds go, it is known that the above bound on $D(n)$ is tight, i.e. $D(n) = \Omega(\log(n)/n)$.

However, even better bounds are possible if we work directly with $M(n)$. Let $n(\epsilon)$ be the size of the smallest point set $P$ such that $M(P) \le \epsilon$ (this is called an $\epsilon$-net). Then it is known that $n(\epsilon) = O(\frac{1}{\epsilon}\log \log \frac{1}{\epsilon})$, which implies that $M(n) = O(\log \log(n)/n)$.

(Note that the $\epsilon$-nets literature usually works with discrete range spaces, but because the bounds on $n(\epsilon)$ are a function of $\epsilon$ only, we can just take an arbitrarily fine discrete approximation of $[0,1]^2$.)