Abstract
A k-clustering of a given set of points in the plane is a partition of the points into k subsets ("cluster"). 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.
Original language | English |
---|---|
Pages (from-to) | 341-356 |
Number of pages | 16 |
Journal | Journal of Algorithms |
Volume | 12 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1991 |