Let $C$ be the square $[-1,1]^2$. Let $a\_1,\dots,a\_m$ be points chosen independently and uniformly at random from $C$. Let $d\_m$ (dispersion) be the random variable $\max\_{x \in C}{\min\_{j \in [m]}{\|x-a\_j\|\_2}}$. I would like to find a function $\epsilon(m)$ such that $\Pr[d\_m \leq \epsilon(m)] \geq $ constant (no dependence on m).


In computational geometry terminology, this means, find an $\epsilon(m)$ such that a "random" $m$-subset of $C$ is an $\epsilon(m)$-net for $(C,\mathcal{B})$ (where $\mathcal{B}$ is the class of all $L\_2$-balls in $\mathbb{R}^2$) with constant probability.


In the one-dimensional case (here $C = [-1,1]$), we can take $\epsilon(m)$ to be $K\frac{\log m}{m}$ for a large enough constant $K$. This follows from Theorem 3.1 of "On the lengths of the pieces of a stick broken at random (Holst, 1980)".


I found [this](https://mathoverflow.net/questions/317410/mean-maximum-distance-for-n-random-points-on-a-unit-square?rq=1) similar question on mathoverflow, about the expected value of maximum distance between any two points in $\{a\_1,\dots,a\_m\}$. I don't see how the bound there can be used to get an $\epsilon(m)$ though.


On page 2 of the paper "Quasi-Monte-Carlo methods and the dispersion of point sequences (Rote-Tichy, 1996)" it says that "If the range space $R$ has finite Vapnik-Chervonenkis dimension $d$ then a random subset of $X$ [to be thought of as $C$ in our question] of size $(d/\epsilon)\log (1/\epsilon)$ is an $\epsilon$-net with high probability." This would be great for us as $\mathcal{B}$ (the class of all $L\_2$-balls in $\mathbb{R}^2$) has finite VC dimension ($= d+1$ for the $d$-dimensional case). Rote-Tichy says that this is proved in the paper "Epsilon-nets and simplex range queries (Haussler-Welzl, 1987)". But on this paper, I could only find such theorems for random subsets of a *finite* $A \subset X$ (Theorem 3.3, Corollary 3.7, etc.).



Dispersion of a "random" subset of $[-1,1]^2$
For every constant dimension $d$, (I.e. when $C = [0,1]^d$), the answer is asymptotically $\varepsilon\_d(m) = \Theta\left(\frac{\log m}{m}\right)^{1/d}$. In the $\Theta$ notation I’m hiding constant factors that depend on $d$. This follows from the [coupon collectors problem](https://en.wikipedia.org/wiki/Coupon_collector%27s_problem): let us partition a $[0,1]^d$ cube into $\varepsilon^{-d}$ sub-cubes of side-length $\varepsilon$, I.e. $[0,1]^d = \left( \bigcup\_i [i \varepsilon, (i + 1) \varepsilon]\right)^d$.


Now, let us draw $m$ points uniformly at random from $[0, 1]^d$, and let’s keep track of which sub-cubes are being hit.


By coupon collectors, as soon as $m \gg \varepsilon^{-d} \log(\varepsilon^{-d})$, with high probability we will hit each sub-cube, and when $m \ll \varepsilon^{-d} \log(\varepsilon^{-d})$ with high probability we will miss at least one sub-cube.


Now it is enough to show the following two elementary geometric fact:


1. Any subset $S\subset [0, 1]^d$ which misses at least one sub-cube, has dispersion at least $\varepsilon/2$ (take the center of a missed cube as a witness $x$).
2. Any subset $S \subset [0,1]^d$ which hits every sub-cube has dispersion at most $\sqrt{d}\varepsilon$ (the diameter of a cube of side length $\varepsilon$).


Related: I recommend the [great answer](https://mathoverflow.net/a/442259/468679) by Iosif Pinelis with much more precise calculation of the exact constant for the case where $d=1$.


