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):
Let $rep_1$ be an arbitrary point in $X$ (a representative for the first cluster).
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$
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?