# Testing of Clustering of points in metric space in sub-linear time

I am trying to understand this paper, in which (k, b)-clusterability is defined like so:

A set $$X$$ of points in a metric space is (k, b)-diameter clusterable if $$X$$ can be partitioned into $$k$$ subsets (clusters) such that the maximum distance between any pair of points in a cluster is $$b$$.

The paper offers an algorithm that always succeeds to Accept (k-b)-clusterable sets which states:

Algorithm 1 (in page 4):

1. Let $$rep_1$$ be an arbitrary point in $$X$$ (a representative for the first cluster).

2. $$i=1$$ $$find\_new\_rep=True$$

3. While $$i and $$find\_new\_rep==True$$

3.1 Uniformly and independently select a sample of size $$ln(3k)/\epsilon$$

3.2 If there exists a point $$x$$ in the sample, such that $$dist(x, rep_j)>b$$ for every $$j\le i$$, then $$i=i+1$$; $$rep_i=x$$

3.3. Else (all points in the sample are at distance at most b from some $$rep_j$$), $$find\_new\_rep = False$$

4. If $$i\le k$$ Accept, Else Reject.

I am struggling with the very first part of the proof (Theorem 1 in page 4):

We first observe that the algorithm rejects only if it finds $$k+1$$ points whose pairwise distances are all greater than $$b$$. Therefore, if $$X$$ is (k, b)-clusterable, then the algorithm never rejects.

What I seem to miss is why can't the algorithm select "wrong" representatives, such that a chosen representative would not allow a clustering to $$k$$ clusters?

Why can't the algorithm find $$k+1$$ representatives? (k, b)-clusterability only means there exists a partition to $$k$$ clusters, why does the algorithm finds that partition?

• I didn't read that paper, but my best guess would be that it might be possible to select "wrong" representatives, but the probability to do so is low. Jul 1, 2021 at 13:48
• @nirshahar No, the probability is exactly 0, as stated in the phrase "never rejects". This is called one-sided-error. The algorithm is sometimes wrong on rejecting epsilon-far from (k, 2b) sets, but this is not important for this question so I omitted it here. Jul 1, 2021 at 13:50

There are no "wrong" representatives assuming that $$X$$ is $$(k,b)$$-clusterable.

Think of it like that: $$X$$ can be divided into $$k$$ clusters. Say you chose some arbitrary node $$x\in X$$ to be a representative (doesn't matter which point!). Then, denote for any cluster $$C$$ such that $$x\in C$$, we know that for any two points $$a,b\in C_x$$, $$dist(a,c)\le b$$. In particular, for any other point $$y\in C$$, we have $$dist(x,y)\le b$$. This means that all nodes in $$C$$ will never be a new representative.

If at the end there were $$k+1$$ representatives, then by the pigeon hole principle, two representatives must be in the same cluster, but this is impossible as we have just shown.

Hence, for $$(k,b)$$-clusterable sets, there will always be at most $$k$$ different representatives, and the algorithm always accepts.

• I'm having difficulty with the phrase "the cluster in $X$ ...". Why is there only one such cluster? Jul 1, 2021 at 14:30
• It doesn't matter. The idea actually works better if $x$ is in more than one cluster. But anyways, usually when we partition a set into clusters it means the following: 1) every element in $X$ is in some cluster 2) any two clusters are disjoint. Under this definition, there really is only one cluster in $X$ that $x$ resides in. Jul 1, 2021 at 14:32
• The point is that $x$ is in some cluster, and all points in that cluster cannot be new representatives. If $x$ is in more than one cluster, then even more elements cannot be new representatives. Jul 1, 2021 at 14:33
• My point is that, there is some optimal clustering, which has $k$ clusters. I fail to see if the clustering is not unique, why the algorithm would necessarily find that clustering. The answer above does not show this, because of the assumption of uniqueness, which may hold, but I fail to see it. Jul 1, 2021 at 14:35
• That last comment should be the answer IMO, it is as clear as it gets (-the pigeonhole principle). Thanks! Jul 1, 2021 at 15:50