Consider a set of $n$ points in $R^d$ which are covered by some finitely many (say $k$) unit balls. Can we approximate the value of $k$ by querying only sublinear many points. More precisely, by sampling $poly(\frac{1}{\epsilon},\mathcal{o(n)})$ points from the set, algorithm outputs some good enough approximation of $k$ i.e., $\lceil{k(1+\epsilon)\rceil}$.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This problem is known as Geometric Set Cover (which deals with covering with different shapes, so unit balls are a special case). I'm unaware of any relation to $k$-means which is a clustering algorithm whose clusters are not limited in radius.
The problem is known to be NP-complete for $k\geq 2$.
For unit balls, this problem has a PTAS ( ($1+\epsilon$)-approximation) ) for the 2D case and is known to be APX-hard for $d=3$.
