pp. 325-326:
Minimax diameter clustering.
Form of partitioned clustering.
Want to minimize the maximum diameter of any cluster.
Farthest-point clustering for any metric space [T. Gonzales,
Clustering to minimize the maximum intracluster distance,
Theoretical Computer Science, 38:293-306, 1985]:
start with an arbitrary point s1.
Pick a point s2 that is as far from s1 as possible.
Pick si to maximize the distance to the nearest of
all centroids picked so far.
That is: maximize the min{dist(si,s1), dist(si,s2), ...}.
After all k representatives are chosen we can define
the partition of S: cluster Sj consists of all points closer to
sj than to any other representative.
Theorem: Let the maximum diameter of this k clustering C_Gon
be D, then even in the optimal k clustering C_opt
the maximum diameter must be at least D/2.
Here optimal is in the sense of minimizing the maximum diameter of any cluster.
Proof: C_gon has centroids s1, ..., sk.
Add one more point q using farthest-point clustering.
Let E be the minimum distance from q to any s1, ..., sk.
Now, by construction, all the other centroids must be at least
E apart from one another.
Therefore, if we are creating an
optimal k-clustering, because we must include these k+1 points,
some cluster X must have two of these points and those
two points must be at least E apart.
So, the lower bound on the optimal clustering is a diameter of E.
Now, consider C_gon. Point q must be in the cluster Y of some centroid
si, so that cluster must have radius at most E and hence diameter
at most 2E.
No other point in any cluster of C_gon can be farther from
its centroid by construction of q.
Fast implementation: clusters points into rectangular boxes
and then simply compute from the rectangle.
Remarkably there is a further theorem that says that it is NP-hard
to do any better than a factor of 1.962 (this result is only for
Euclidean).