Largest rectangle not touching any rock in a square field

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.

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