Vasilis Capoyleas, Günter Rote, and Gerhard Woeginger:
Geometric clusterings
-
Extended abstract in: Proceedings of the Second Canadian Conference
on Computational Geometry, Ottawa, August 6-10, 1990. Editor: J. Urrutia;
pp. 28-31.
-
Journal of Algorithms 12 (1991), 341-356, (Zbl 734.68092, MR #92d:52033).
Abstract
A k-clustering 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 k-clustering 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 3-clustering, an improved algorithm was later given in the paper
Three-clustering
of points in the plane.)
Last update: April 5, 2002.