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).