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

Question

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<k+1$ 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?

Answer 1

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.