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

Geometric clusterings

  1. Extended abstract in: Proceedings of the Second Canadian Conference on Computational Geometry, Ottawa, August 6-10, 1990. Editor: J. Urrutia; pp. 28-31.
  2. Journal of Algorithms 12 (1991), 341-356, (Zbl 734.68092, MR #92d:52033).


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

  PostScript file (gzippedpdf file (gzippedTeX .dvi file (gzipped)
other papers about this subject
Last update: April 5, 2002.