Let $C\_n$ be the hypercube $[-1,1]^n$. For $a\_1,\cdots,a\_s \in C\_n$, define its dispersion $D(a\_1,\cdots,a\_s)$ as $\max\_{x \in C\_n}\min\_{i \in [s]} \|x-a\_i\|\_{2}$. Let $0< \lambda < 1$ be a constant. How small can $s(n)$ be so that
$$
\lim\_{n\rightarrow \infty}\{ \Pr\_{a\_1,\cdots,a\_s \sim C\_n}\left[ D(a\_1,\cdots,a\_{s}) \leq \lambda \right] \} \geq 2/3 \;?
$$


**Upper bound**: $O(n^{cn})$ for some constant $c$


*Proof*: Divide $C\_n$ into subcubes, each with side length $l$. The number of subcubes is $\left(\frac{2}{l} \right)^n$. By Coupon Collector's, if $s(n) = \left(\frac{2}{l} \right)^n\log\left(\left(\frac{2}{l} \right)^n \right) + K\left(\frac{2}{l} \right)^n$ (for a large enough constant $K$), then all subcubes will be hit with probability at least $2/3$. If all subcubes are hit, the dispersion is at most $\frac{l\sqrt{n}}{2}$. Taking $l=\frac{2\lambda}{\sqrt{n}}$, we get an $O(n^{cn})$ upper bound.


**Lower bound**: $\Omega(e^{cn})$ for a constant $c$


*Proof*: Divide $C\_n$ into subcubes, each with side length $l$. By Coupon Collector's, if $s(n) = \left(\frac{2}{l} \right)^n \log\left(\left(\frac{2}{l} \right)^n \right) + k\left(\frac{2}{l} \right)^n$ (for some small enough constant $k$), then the probability of hitting all subcubes is at most 0.6. Hence, the probability of missing at least one subcube is greater than 0.4. If you miss at least one subcube, then the dispersion is greater than $\frac{l}{2}$. Hence,
$$
\lim\_{n\rightarrow \infty}\{ \Pr\_{a\_1,\cdots,a\_s \sim C\_n}\left[ D(a\_1,\cdots,a\_{s}) \leq \frac{l}{2} \right] \} \leq 0.6 .
$$
Taking $l = 2\lambda$, we get an $\Omega(e^{cn})$ lower bound.



How many samples do you need to get constant dispersion?
The packing number of the cube with L2 balls of radius $\lambda$ is at least $ \lambda^{-n} C^n (n/2)! \approx \lambda^{-n} C^n n^{n/2} $. By the argument you had before you get the upper bound in the question is tight.


