On Approximate Geometric k -Clustering

For a partition of an n -point set into k subsets (clusters) S ₁ ,S ₂ ,. . .,S _k , we consider the cost function , 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 ε . Received October 19, 1999, and in revised form January 19, 2000.