Lloyd's method terminates when the data partition agrees with the Voronoi partition defined by the centers; as such, Voronoi diagrams are typically associated with k-means clustering.

In "Hartigan's Method: k-means without Voronoi" (Telgarsky and Vattani, to appear in AISTATS 2010), it is shown that there is another family of sets, lovingly termed the circlonoi partition, which the points must agree with for the k-means optimum to be reached. This is found by analyzing Hartigan's method, which proceeds point by point, but allows points to move to centers which are slightly farther away than their current centers; the method halts only if the data agrees with its circlonoi partition.

The interactive figure below is meant demonstrates these notions. Apologies in advance: google chrome is required.

• Points are represented by circles, cluster centers by x's. Cliques are formed out of clusters.
• To move a point, drag it.
• To delete a point, drag it out of the canvas.
• The "radii" indicate points which will change cluster assignment after an iteration of Lloyd or Hartigan. If a point can be reassigned by Lloyd, then a black and white line segment will extend from the point and reach the center. If only the white extension (which has a black bar at the end) can reach the center, then only Hartigan's method can iterate. Please see section 2.2. (Points which will inhabit an empty cluster are not marked.)
• The "inner Voronoi" shows the fringe of the Voronoi cells which is lower bounded in theorem 3.1.
• When the number of points becomes large, the circlonoi boundary becomes somewhat inaccurate. This is because the circlonoi cell radius is huge, but the allowed error at the boundary becomes tiny; this leads to floating point problems.