We say a set of $n$ points in $R^d$ are $k$-clusterable, if all points are covered by k unit balls. We have a property testing algorithm (see section 5 of paper) which consider a promise version of the above problem. The algorithm samples $O(\frac{kd}{\epsilon}\log \frac{kd}{\epsilon})$ many points from the set, and distinguish between following two cases with probability at least $\frac{2}{3}$:

-algorithm ACCEPTS, if all the points are $k$-clusterable.

-algorithm REJECTS, if points are $\epsilon$-far from $k$-clusterable, i.e. any $k$ unit balls covers at most $(1-\epsilon)n$ points.

Now, using the above algorithm as a subroutine can we approximate the value of $k$ (number of clusters), i.e., if we can ignore at most $\epsilon n$ points (because now we don't have the promised version of the input) from the input, then we need to determine the number of clusters in the input.

(I was thinking to do some kind of binary search over $k$, start with k=2, if algorithm ACCEPTS then k=2, if REJECTS then try for k=4 and so on.)

Pls let me know if there is any confusion in the problem.

  • 3
    $\begingroup$ What are you asking? $\endgroup$
    – R B
    Sep 1, 2014 at 6:57
  • $\begingroup$ @RB We have given (as a black-box) a set of points which are clustered, but we don't know the number of clusters. Our goal is to find an approximate value of $k$ just by looking only sublinear/$O(1)$ many points, and using testing algorithm algorithm as subroutine. $\endgroup$
    – Ram
    Sep 1, 2014 at 7:02
  • 1
    $\begingroup$ @Ram: do you know a reasonable upper bound $K$ on $k$? (by default, $K=n$ works, but it will introduce a dependence on $n$, namely $\log\log n$). For the binary search, wouldn't the following work: set $\delta=1/(3\log K)$, and amplify the probability of success of the subroutine to $1-\delta$ by standard techniques (blowup of a factor $\log(1/\delta)$ in the sample complexity). Then try $k=1,2\dots,K$ (wlog, $K$ is a power of $2$), and take $k^\ast$ to be the last value for which the test accepts. With probability at least $1-K\delta=2/3$, you got a 2-approximation of the "right $k$". $\endgroup$
    – Clement C.
    Sep 1, 2014 at 15:12

1 Answer 1


First. One can do better as far as the sampling - at least if $d$ is large - $O(\frac{kd \log k}{\epsilon} \log \frac{1}{\epsilon})$ should follow easily from relative approximations http://sarielhp.org/p/06/relative/ and combining range spaces of bounded VC dimension (if you send me email I would email you a pdf containing this combining result you need - its well known, but i dont know a ref for that). Secondly, relative approximation sample in this case, guarantees that if the sample fails, then $k$ is too small. So, do exponential search for the right value of $k$, specifically, start with $k_i = 2^i$, and let $R_i$ be the the $i$th sample of size $n_i = O( \frac{kd \log k}{\epsilon} \log \frac{i}{\epsilon} )$ (the $i$ is not a typo).

Let $\alpha$ be the minimum $i$ for which the sample succeeds using the black box. Now, use brute force (on the sample) to find the minimum $k\leq k_\alpha$ for which the sample works. And this is your desired $k$. You need to carefully account for the probability of success, but thats why the $i$ is there - its one of these standard geometric summation stuff.

The $i$ can be avoided -- indeed, the probability that $\alpha$ is bigger by $\Delta$ than its correct value is smaller than $2^{-\Delta}$. If you do that, then the sample you are going to use is of the right size with good probability. That is, if the minimum $k$ for which you can cover more than $(1-\epsilon)n$ of the points is $\kappa$, then the sample the algorithm uses is $O\left( \frac{\kappa d \log \kappa}{\epsilon} \log \frac{1}{\epsilon} \right)$.

There is some added fuzzyness in the answer of this algorithm. The returned answer $\kappa$ is the minimum such that any value of $k < \kappa$, is say $(1-\epsilon/2)$-far from from being k-clustered. I assume this is OK.

In practice you would do something different. Hmm. Something to think about....

  • $\begingroup$ Just to be certain I understand -- in the expression of $n_i$, the $k$'s are $k_i$'s, aren't they? $\endgroup$
    – Clement C.
    Sep 3, 2014 at 11:30
  • $\begingroup$ @Sariel Har-Peled Thanks for your reply! But, I don't see any easy proof of the following claim: If a set of points are $\kappa$-clustrable, then $\forall$ $k<\kappa$, points are $(1−\frac{\epsilon}{2})$-far from from being $k$-clustered. Could you suggest some intuition or some reference to prove the claim. $\endgroup$
    – Ram
    Sep 4, 2014 at 8:02
  • $\begingroup$ Shouldn't this be not κ-clustrable? $\endgroup$ Sep 6, 2014 at 18:01

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.