Lloyd's k-means algorithm with explicit tie handling

Input. Let $n,p$ be positive integers, let $1\le K\le n$, let $x_1,\dots ,x_n\in {\mathbb{R}}^p$, and supply initial centers ${\mu }_1^{(0)},\dots ,{\mu }_K^{(0)}\in {\mathbb{R}}^p$.

Initialization. Assign each $x_i$ to a nearest initial center, choosing the smallest center index in a tie. Denote these labels by $z_i^{(0)}$.

Iteration. For $t=0,1,2,\dots$:

1. With the current centers fixed, assign each $x_i$ to a nearest center. If its current label $z_i^{(t)}$ is among the nearest-center indices, retain $z_i^{(t)}$; otherwise choose the smallest nearest-center index. Call the resulting labels $z_i^{(t+1)}$.
2. For each nonempty cluster $C_k^{(t+1)}:=\{i:z_i^{(t+1)}=k\}$, set ${\mu }_k^{(t+1)}:=\frac{1}{\mathrm{\mid }{C}_k^{(t+1)}\mathrm{\mid }}{\sum }_{i\in C_k^{(t+1)}}{x}_i\mathrm{.}$ If $C_k^{(t+1)}$ is empty, set ${\mu }_k^{(t+1)}:={\mu }_k^{(t)}$.
3. If both $z^{(t+1)}=z^{(t)}$ and ${\mu }^{(t+1)}={\mu }^{(t)}$, return these labels and centers. Otherwise continue with the updated labels and centers.

The procedure makes no global-minimization claim. Its termination under these tie rules is proved separately.