The k-means method is a widely used technique for clustering points in Euclidean space.  While it is extremely fast in practice, its worst-case running time is exponential in the number of data points. We prove that the k-means method can implicitly solve PSPACE-complete problems, providing a complexity-theoretic explanation for its worst-case running time.  Our result parallels recent work on the complexity of the simplex method for linear programming.
['Tim Roughgarden', 'Joshua R. Wang']
The Complexity of the k-means Method