On Approximate Geometric k -Clustering

For a partition of an n -point set \(X\subset \Rd\) into k subsets (clusters) S ₁ ,S ₂ ,. . .,S _k , we consider the cost function \(\sum_{i=1}^k \sum_{x\in S_i} \|x-c(S_i)\|^2\) , where c(S _i ) denotes the center of gravity of S _i . For k=2 and for any fixed d and ε >0 , we present a deterministic algorithm that finds a 2-clustering with cost no worse than (1+ε) -times the minimum cost in time O(n log n); the constant of proportionality depends polynomially on ε . For an arbitrary fixed k , we get an O(n log^k n) algorithm for a fixed ε , again with a polynomial dependence on ε .

Authors and Affiliations

1. Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic matousek@kam.mff.cuni.cz, , , , , , CZ

   J. Matoušek

Received October 19, 1999, and in revised form January 19, 2000.

Reprints and permissions