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

• Just out of curiosity, where does this problem come from? (+1) – A.P. Nov 17 '15 at 21:32
• @A.P. It comes from my Ph.D. research about fair division of land. See my profile :) – Erel Segal-Halevi Nov 17 '15 at 21:37
• Is it necessary that the house be aligned with the grid (e.g. to align with a road or the cardinal directions)? – Marconius Nov 17 '15 at 21:40
• @Marconius actually, the two variants of this problem are interesting, and the bounds are probably different. For example, in the figure I added, the area of the largest axis-parallel rectangle is approximately $1/(4 \sqrt{n})$, but the area of the largest rotated rectangle is approximately $1/\sqrt{n}$. – Erel Segal-Halevi Nov 17 '15 at 21:46
• When $n=2$, the points are $(1/\phi, 1/\phi)$ and $(1-1/\phi, 1-1/\phi)$ with area $1-1/\phi$ where $\phi$ is the golden ratio. – Ben Longo Dec 19 '15 at 20:38

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.

• Thanks! Is it the same paper here? stetson.edu/~efriedma/mathmagic/0899/ravsky.ps The problem in your paper seems very similar to my problem, with one difference: your function, $T(n)$, is a supremum (on all possible n-tuples of points), while I defined it as an infimum. Apparently, the supremum is always 1, as it is always possible to select $n$ points on the boundary of the unit square. Is there anything I misunderstand? – Erel Segal-Halevi Dec 19 '15 at 19:45
• N.B. You also refer to question 3 in this page: www2.stetson.edu/~efriedma/mathmagic/0899.html where he defines T(n) as "minimum area". I am a bit confused. Is this minimum or maximum? – Erel Segal-Halevi Dec 19 '15 at 19:48
• @ErelSegal-Halevi The problem which considered Friedman and I is the same as yours. So in my definition of $T(т)$ should be $\inf$ instead of $\sup$ (there is a misprint (the paper was not reviewed :-) )). Thanks for your attentivity. – Alex Ravsky Dec 20 '15 at 6:02
• In this case, this is indeed the same problem. Thanks! – Erel Segal-Halevi Dec 20 '15 at 13:13

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