Two steps, repeated. That is the whole algorithm.
Assign every point to the nearest centre. Move every centre to the average of the points assigned to it. Repeat until nothing changes. That is k-means, and pressing Assign and Update alternately is literally running it.
Each of those two steps can only ever decrease the inertia — the total squared distance from points to their own centre — so the algorithm always converges. What it converges to is another matter entirely, and that is the interesting part.
It finds a local optimum, and often not a good one
Load One diffuse blob + four dense ones with k = 5 and random initialisation, then press Re-seed a few times and run it. Sometimes it puts one centre in each dense blob and one in the diffuse one — the answer anybody would draw. Sometimes two centres end up splitting the big diffuse blob while two dense blobs get merged under a single centre, and the algorithm is perfectly happy: no single point can improve by moving, so it stops.
The restart experiment counts how often that happens. On a dataset built along these lines, 47.5% of random initialisations ended up worse than 1.9 times the best inertia found, with a mean inertia of 1827 and a standard deviation of 1447 — the spread nearly as large as the value itself. With k-means++ initialisation the same measurement gave 1%. That experiment is written up here.
The button above runs the same comparison live, on a freshly sampled dataset, in your browser. The rates will not match those figures — the data is not the same data, and the exact percentages are extremely sensitive to how far apart the dense blobs are — so the thing to read is the gap between the two histograms, not either number on its own. On the preset loaded here, random initialisation typically misses the best answer several times more often than k-means++ does.
What k-means++ actually does
It is a two-line change. Pick the first centre uniformly at random. For every subsequent centre, pick a point with probability proportional to the square of its distance to the nearest centre already chosen. That is all.
The effect is that centres start far apart, so two of them rarely land inside the same blob — which is the failure that produces almost every bad local optimum. It costs one extra pass over the data per centre, it comes with a proof that the expected result is within O(log k) of optimal, and it is the default in scikit-learn for exactly these reasons. If you are running k-means with random initialisation and only one restart, this is the single change that will most improve your results.
Where k-means is the wrong tool entirely
Load Two moons. There is no value of k and no initialisation that will separate the two crescents, because k-means partitions space with straight boundaries — the cells it produces are always a Voronoi diagram of the centres, so every cluster is convex. Two interlocking crescents are not convex, so the answer is unreachable in principle rather than by bad luck.
Stretched blobs shows the milder version of the same problem: k-means minimises squared Euclidean distance, which means it prefers clusters that are round and similarly sized. Give it long thin ones and it will cut them across the middle instead of along their length. When that happens, the answer is not more restarts — it is a different algorithm.