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 $k$-means
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 $k$-means 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.