Vasilis Capoyleas, Günter Rote, and Gerhard Woeginger:
Geometric clusterings

Extended abstract in: Proceedings of the Second Canadian Conference
on Computational Geometry, Ottawa, August 610, 1990. Editor: J. Urrutia;
pp. 2831.

Journal of Algorithms 12 (1991), 341356, (Zbl 734.68092, MR #92d:52033).
Abstract
A kclustering of a given set of points in the plane is a partition
of the points into k subsets ("clusters"). For any fixed k,
we can find a kclustering which minimizes any monotone function
of the diameters or the radii of the clusters in polynomial time. The algorithm
is based on the fact that any two clusters in an optimal solution can be
separated by a line.
(For 3clustering, an improved algorithm was later given in the paper
Threeclustering
of points in the plane.)
Last update: April 5, 2002.