Understanding contradiction in proof of Algorithm for 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 rejects A set $X$ if it is $\epsilon-far$ from (k-2b)-clusterable with probability > $\frac{2}{3}$.

$\epsilon-far$ from (k-2b)-clusterable here means that at least $\epsilon |X|=\epsilon n$ points must be deleted from $X$ in order to make it (k-2b)-clusterable.

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 last part of the proof (Theorem 1 in page 4):

... Hence, from now on, assume that $X$ is $\epsilon$-far from $(k, 2b)$ -clusterable ...
Consider any particular iteration. We say that a point $x \in X$ is a candidate representative with respect to $rep_1, ..., rep_i$ if it has distance greater than $b$ from each of these points. We claim that as long as $i \le k$ there must be more than $\epsilon n$ such candidate representatives. Assume in contradiction that there are at most $\epsilon n$ such points. Then we could remove these points from $X$, and for every other point $y \in X$, assign y to a cluster $j$ such that $dist(y, rep_j) \le b$. By the triangle inequality, the diameter of each resulting cluster is at most $2b$, which contradicts out assumption concerning $X$.

What I seem to miss is what is the contradiction?

I can see why every cluster is of diameter $2b$, but I don't see why ignoring all far points, and adding the rest to some valid clusters gives anything not OK.

Would love some direction as I have been staring at this for hours.

Answer 1

From what I understand, the problem the paper is trying to solve is a gap problem of deciding whether $X$ is $(k,b)$-clusterable, or at least $\epsilon$-far from being $(k,2b)$-clusterable. Since they explained why the algorithm always accepts when $X$ is $(k,b)$-clusterable, now they move on to explain what happens when $X$ is at least $\epsilon$-far from being $(k,2b)$-clusterable.

Now, their job is to show that there are a lot of candidates in $X$ at any point in time (so the probability of choosing at least one will be high). They assume towards contradiction this is not the case. That is, they assume that sometime they reach a state where there are less than $\epsilon \cdot n$ candidates. Here comes the tricky part: They want to show this contradicts the fact we know $X$ is $\epsilon$-far from being $(k,2b)$-clusterable, so they remove the $\epsilon \cdot n$ candidates from $X$, and explain why we are left with at most $k$ clusters of size $2b$: Each $y\in X$ that is left, is not a candidate. Hence, there must be some representative $rep_i$ such that $dist(y,rep_i)\le b$. They define the clusters to be balls with radius $b$ around all those representatives, and overall each point $y$ must be in at least one ball. The balls have a radius of $b$, so the distance between any two points in them is at most $2b$ (the diameter of the ball). Therefore, they found a $(k,2b)$-clustering of $X$ when we remove those $\epsilon \cdot n$ points. But since $X$ was assumed to be far from such a clustering (you need to remove more than $\epsilon \cdot n$ to convert it into something clusterable), this contradicted that assumption.

Hence, they conclude that at each point in time there are at least $\epsilon \cdot n$ possible candidates.