18
$\begingroup$

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?

enter image description here

$\endgroup$
  • 2
    $\begingroup$ Just out of curiosity, where does this problem come from? (+1) $\endgroup$ – A.P. Nov 17 '15 at 21:32
  • 1
    $\begingroup$ @A.P. It comes from my Ph.D. research about fair division of land. See my profile :) $\endgroup$ – Erel Segal-Halevi Nov 17 '15 at 21:37
  • 1
    $\begingroup$ Is it necessary that the house be aligned with the grid (e.g. to align with a road or the cardinal directions)? $\endgroup$ – Marconius Nov 17 '15 at 21:40
  • 2
    $\begingroup$ @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}$. $\endgroup$ – Erel Segal-Halevi Nov 17 '15 at 21:46
  • 2
    $\begingroup$ 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. $\endgroup$ – Ben Longo Dec 19 '15 at 20:38
3
+50
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Erel Segal-Halevi Dec 19 '15 at 19:45
  • 1
    $\begingroup$ 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? $\endgroup$ – Erel Segal-Halevi Dec 19 '15 at 19:48
  • $\begingroup$ @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. $\endgroup$ – Alex Ravsky Dec 20 '15 at 6:02
  • 1
    $\begingroup$ In this case, this is indeed the same problem. Thanks! $\endgroup$ – Erel Segal-Halevi Dec 20 '15 at 13:13
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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