We present polynomial upper and lower bounds on the number of
iterations performed by Lloyd's method for k-means clustering.
Our upper bounds are polynomial in the number of points, number of
clusters, and the spread of the point set. We also present a
lower bound, showing that in the worst case the \kmeans{}
heuristic needs to perform Omega(n) iterations, for
n points
on the real line and two centers. Surprisingly, our construction
spread is polynomial. This is the first construction
showing that the \kmeans{} heuristic requires more than a
polylogarithmic number of iterations. We also present alternative
algorithms, with guaranteed performance, which are simple variants
of Lloyd's method. We also performed experimental study of the
performance of those algorithms.