3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.