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.

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.

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.