How to cover n sites with the smallest number of fixed radius balls?

Question

Given $n$ "data points" in $d$ (Euclidean) space

$$\mathbf{x}_j \in \mathbb{R}^d, \text{ for } j \in \{1,\dots,n\}$$

how does one find the smallest integer $m$ such that there exists $m$ "centre points"

$$\mathbf{c}_i \in \mathbb{R}^d, \text{ for } i \in \{1,\dots,m\}$$

where for each data point the closest centre is within a given radius $r$

$$r^2 \ge \min^{m}_{i=1} \|\mathbf{x}_j - \mathbf{c}_i\|^2, \forall j \in \{1,\dots,n\} $$

?

I think this is similar to or the same as the geometric set cover problem. In my case, the centre locations are not drawn from a discrete set but rather they are free points in $\mathbb{R}^d$.

I have a "bottom-up" merge-based heuristic that seems to work well in 2D, but would like to know if any known algorithms exist.

Answer 1

If we take your given radius $r$ to be $1$, I believe your problem is known as covering points by unit balls, or the unit covering problem. Covering by two unit balls was shown to be NP-complete by Megiddo, by reduction from 3SAT:

Megiddo, Nimrod. "On the complexity of some geometric problems in unbounded dimension." Journal of Symbolic Computation 10.3-4 (1990): 327-334. (PDF download.)

However, a polynomial-time approximation scheme (PTAS), in any fixed dimension, is available:

Hochbaum, Dorit S., and Wolfgang Maass. "Approximation schemes for covering and packing problems in image processing and VLSI." Journal of the ACM (JACM) 32.1 (1985): 130-136. (PDF download.)

Many variations have been studied, e.g., "capacitated covering with unit balls," where the points have weights and each covering ball can cover no more than a weight sum of $1$; or versions that involve coloring restrictions.

---

         
          ^{Image from StackOverflow post by user dfens.}

---