Computing $\epsilon$-packing sets in Euclidean space

26 Views Asked by At

Let $\epsilon > 0$. For $P\subset \mathbb R^d$, a subset $Q\subset P$ is called an $\epsilon$-packing if:

  1. for every $p \in P$ there is a $q\in Q$ such that $d(p,q) \leq \epsilon$, and
  2. for every $q, q' \in Q$, we have $d(q,q') \geq \epsilon$. (See also the definitions here).

Question. What algorithms exist for computing a maximal $\epsilon$-packing of, e.g., a Euclidean sphere $S^{d-1}\subset \mathbb R^d$?

I did some Googling and have only came up with algorithms for computing packings, coverings, nets, etc., in finite metric spaces, e.g., in this paper.

But how does computing such sets work for continuous subsets of Euclidean space? Do we first need to replace the set with some finite model, or can it be done directly?