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}$.


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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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