Scatter a few centres among points; assign each point to its nearest centre, then move each centre to the average of its points, and repeat. The centres drift into evenly-spaced cells — a centroidal Voronoi tessellation. It is exactly the k-means loop, and it relaxes the diagram Fortune (098) builds.
THE TECHNIQUE nearest centre, then the mean, then again
Two steps, alternated: assign each point to its nearest centre (a Voronoi partition), then update each centre to the centroid (mean) of the points assigned to it. Each round lowers the total within-cell distance, so it converges to a stable, evenly-spread set of centres. Watch the centres relax into place. live demo
HISTORY & CREDIT unpublished for a quarter century
“k-means, MacQueen 1967” — MacQueen invented named it; the algorithm is Lloyd’s (1957), and Steinhaus’ even earlier. cited
1956 · Hugo Steinhaus gives the continuous version — partition to minimise within-cluster variance. 1957 · Stuart Lloyd (Bell Labs) devises the assign-and-average method for PCM quantisation — and leaves it in an internal memo, unpublished until 1982. For 25 years it was reinvented by others. 1960 / 1965 / 1967 · Max (independently, “Lloyd-Max quantiser”), Forgy (the batch form), and MacQueen (who coined “k-means”) all arrive at the same loop. the catch · it finds a local optimum — the result depends on where the centres start; k-means++ (2007) seeds them better.
One of the most-used algorithms in the world, sat unpublished in a drawer for a generation. Lloyd 1957 (publ. 1982)
RECOMMEND FOR I-13 distances and means, on parallel arrays
Assign is squared distances, update is sum-then-divide — all f64 over arrays — and one relaxation step lands the exact centroids:
$ i13 run lloyd.i13 # 5 points, 2 centres, one assign+update
c1 -> (1.667, 1.333) c2 -> (4.5, 3.5) # then stable: converged
Recommend:nothing new — hold points and centres as parallel f64 arrays xs[]/ys[], the nearest-centre test is dx*dx+dy*dy with a running argmin (no sqrt needed, squared distance shares the min), and the update is sum-then-divide (verified centroids (5/3, 4/3) and (4.5, 3.5)). The whole loop is in I-13’s comfort zone. Note: the points are (x,y) pairs — the PS-014 pair want — sidestepped by parallel arrays, exactly as Bezier (086) does. It relaxes the Voronoi diagram Fortune (098) builds — a natural pair.