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.

add point
random reassignment Lloyd step Hartigan step
undo reset
circlonoi (section 2.3)
inner Voronoi (section 3.1)
radii (section 2.2)