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

clusters

Voronoi

circlonoi (section 2.3)

inner Voronoi (section 3.1)

radii (section 2.2)

- 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.