Constructing an $\epsilon$-net of $l_2$ unit ball I am interested in probabilistic or explicit ways to construct an $\epsilon$-net of the $l_2$ unit ball in $\mathbb{R}^{d}$.
I know that, for every $\epsilon > 0$, there exists an $\epsilon$-net $\mathcal{N}_{\epsilon}$ for the unit sphere in $d$ dimensions such that
$$
M\triangleq\left|\mathcal{N}_{\epsilon}\right|
\le \left( 1+\frac{2}{\epsilon}\right)^{d}.
$$
(Lemma 5.2 in https://arxiv.org/abs/1011.3027)
To my understanding, the aforementioned bound holds for an $\epsilon$-net of the entire ball, not only the sphere.
In the case of the sphere, we can construct an $\epsilon$-net with high probability, 
by drawing a sufficient number ($O(M\log{M})$) of independent random vectors according to a Gaussian distribution $N(\mathbf{0}, \mathbf{I})$, and normalizing the length to $1$.
I believe that one way to get an $\epsilon$-net for the ball,
would be to repeat the above procedure $O(1/\epsilon)$ times, for all spheres of radii $\epsilon, 2\epsilon,3\epsilon, \dots, 1$.
The union of the $\epsilon$-nets, should be able to cover the ball.
However, it would require $\tilde{O}\left((1+2/{\epsilon})^{d+1}\right)$ points (ignoring the logarithmic factor).


*

*Is there a simple way to construct an $\epsilon$-net for the unit ball directly, $\textit{i.e.}$, without constructing nets for multiple spheres?

*Is there way to achieve the bound on $\left|\mathcal{N}_{\epsilon}\right|$ (possibly up to logarithmic factors)?


I would appreciate any pointers to either probabilistic or explicit methods.
 A: We can use surface area instead of volume.
Let $N_\epsilon$ be a subset of $S^{n-1}$ (embedded in $\mathbb{R}^n$) such that any two points in $N_\epsilon$ have distance strictly greater than $\epsilon$ and $N_\epsilon$ is maixmal. This means that the balls of radius $\epsilon/2$ centered at points in $N_\epsilon$ are disjoint and are contained in $B(0,1+\epsilon/2)$ and are outside the ball $B(0,1-\epsilon/2)$. Let $V(r)$ be the volume of the $n$ dimensional ball of radius $r$ and let $S(r)$ be the surafce area of the ball of radius $r$. Then
\begin{align*}
 |N_\epsilon| V(\epsilon/2) &\le V(1+\epsilon/2) - V(1-\epsilon/2) \\
                                          &= \int_{1-\epsilon/2}^{1+\epsilon/2} S(r) dr \\
                                          &\le \int_{1-\epsilon/2}^{1+\epsilon/2} S(1+\epsilon/2) dr \\
                                          &= \epsilon S(1+\epsilon/2) \\
                                          &= \epsilon (1+\epsilon/2)^{n-1} S(1) 
\end{align*}
Then using the relation between the volume and the surface area, we get that
$$
 |N_\epsilon| \le \epsilon (1+\epsilon/2)^{n-1} \frac{2^n}{\epsilon^n} \frac{S(1)}{V(1)} = 2n \left(1+\frac{2}{\epsilon}\right)^{n-1}. 
$$
Here we gained a factor of $n$ in front, but we reduced the power from $n$ to $n-1$. Hence when $\epsilon$ is small, this is a better bound than the volumetric bound.
A: One can take a random lattice $\Lambda\subset\mathbb R^n$, e.g., a random Construction-A lattice.
It is known that such lattices are good for covering (with high pribability), i.e., $r_{\text{cov}}(\Lambda) = r_{\text{eff}}(\Lambda)(1+o(1))$.
See Theorem 2 here.
(It is pretty nontrivial to prove.)
By covering goodness, if one takes $r_{\text{cov}}(\Lambda) = \epsilon$, then 1) $\Lambda\cap B_2^n$ (where $B_2^n$ is the unit $\ell_2$ ball) is an $\epsilon$-net of $B_2^n$; 2) $|\Lambda\cap B_2^n|\le\frac{\text{vol}(B_2^n+\epsilon B_2^n)}{r_{\text{cov}}(\Lambda)B_2^n}=(1+1/\epsilon)^n$.
Haar lattices should also do the job, though I don't have a reference in mind.
Maybe check out papers by C. A. Rogers.
If you don't like lattices (they're linear and it's hard to prove covering properties), then I'm reasonably confident that a (homogeneous) Poisson point process (with appropriate intensity) restricted to a ball should satisfy your requirements with high probability.
Not sure if this is proved anywhere but it should be much easier to prove than lattices.
As far as I understand, constructing explicit $\epsilon$-nets meeting existential bounds is a hard question.
Theoretical computer scientists may care about it.
See e.g. this, though I did not read it myself.
