Exact finite-data Lloyd quantizer

Input: integers $N,d,k\ge 1$, indexed data $x_1,\dots ,x_N\in {\mathbb{R}}^d$, exact positive weights $w_i$ with ${\sum }_i{w}_i=1$, and an ordered initial center tuple $c^0=(c_1^0,\dots ,c_k^0)\in ({\mathbb{R}}^d{)}^k$. At each pass $t$:

1. Assign index $i$ to the least $j\in \{1,\dots ,k\}$ minimizing $\mathrm{\parallel }{x}_i-c_j^t{\mathrm{\parallel }}_2^2$. Let $S_j^t$ be the indices assigned to $j$.
2. If $S_j^t\mathrm{\ne }\mathrm{\varnothing }$, set $c_j^{t+1}:=({\sum }_{i\in S_j^t}{w}_i{x}_i)\mathrm{/}({\sum }_{i\in S_j^t}{w}_i)$. If $S_j^t=\mathrm{\varnothing }$, set $c_j^{t+1}:=c_j^t$.
3. If $c^{t+1}=c^t$ coordinatewise, return $c^t$ and the assignments from this pass. Otherwise begin the next pass with $c^{t+1}$.

All distance comparisons and arithmetic are exact. Rational input coordinates, weights and initial centers give a rational implementation using exact rational operations. For arbitrary real data this is an exact-real operation model; no bit-complexity claim is part of the procedure.