<p>This problem is known as <em>Geometric Set Cover</em> (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.</p>

<p>The problem is known to be NP-complete for $k\geq 2$.</p>

<p>For unit balls, <a href="https://people.mpi-inf.mpg.de/~saurabh/Papers/localsearch.pdf" rel="nofollow">this problem has a PTAS</a> ( ($1+\epsilon$)-approximation) ) for the 2D case and <a href="http://2011.cccg.ca/PDFschedule/papers/paper102.pdf" rel="nofollow">is known to be APX-hard for $d=3$</a>.</p>

CC BY-SA 3.0
2014-08-25T07:14:34.533Z
2014-08-25T07:23:06.937Z
2014-08-25T07:23:06.937Z
R B
<p>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$ <em>i.e.</em>, $\lceil{k(1+\epsilon)\rceil}$.</p>

<approximation-algorithms><clustering><computational-geometry><sample-complexity>
Approximating the value of k in $k$-mean clustering problem
Ram
# Approximating the value of k in $k$-mean clustering problem

(Asked by: username_0 on 2014-08-25)

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

**Tags:** approximation-algorithms, clustering, computational-geometry, sample-complexity

---

## 1 answers

### Answer by username_1 on 2014-08-25. Score: 3 | Accepted answer

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](https://people.mpi-inf.mpg.de/~saurabh/Papers/localsearch.pdf) ( ($1+\epsilon$)-approximation) ) for the 2D case and [is known to be APX-hard for $d=3$](http://2011.cccg.ca/PDFschedule/papers/paper102.pdf).


---

