Questions about a k-means variant : recompute centroids after each point is reasigned

Question

I have a variant of k-means, where the points are reassigned incrementally and I have a few questions about it.

Each time we reassign a point (we move the point from cluster $C_1 $to $C_2$), we recompute both the centroids of $C_1 $and $C_2$. The centroid of a cluster $C$ is computed as the mean of the points in $C$.

1) Why does it produces k non-empty clusters ?

2) Can you find an exemple where a different order of processing the input points gives different clusterings ?

Thanks for your help !

Answer 1

1) Why does it produces k non-empty clusters ?

It produces non-empty clusters because the last point within a current cluster will never be reassigned since it is the centroid of its own cluster.

Although not producing empty clusters, this variant produces 1-point clusters.