K-means clustering (${\min }_{C_1,\dots ,C_K}{\sum }_{k=1}^K{\sum }_{i\in C_k}\Vert x_i-m_k{\Vert }^2$)

For a prescribed number of groups, minimize within-cluster squared Euclidean distances. At fixed assignments, differentiating the objective gives the mean as the optimal centroid. At fixed centroids, assigning each point to a nearest centroid minimizes its contribution. Alternating these steps cannot increase the objective but can converge to a local optimum, so multiple starts are useful. Empty clusters and ties need an explicit handling rule. The method favors roughly spherical groups and depends on variable scaling.

For $n$ distinct observations on the real line and $1\le K\le n$, nearest-centre assignment produces contiguous blocks of the sorted observations because each Voronoi cell is an interval. The arithmetic means of distinct ordered blocks are strictly ordered, preserving this property at subsequent assignments. Initialize at $K$ distinct observed values so that the initial assignment has no empty cluster.

The empty-cluster repair in finite termination of K-means clustering also preserves contiguous blocks: an observation farthest from a centre over its assigned block lies at one of that block's endpoints, so transferring it to a new singleton splits the block into two contiguous blocks.

There are $\left(\genfrac{}{}{0ex}{}{n-1}{K-1}\right)$ possible partitions into $K$ nonempty blocks: choose $K-1$ cuts among the $n-1$ gaps. Under the stable tie rule in finite termination of K-means clustering, every round after the first strictly reduces the objective until stopping, so a block partition cannot recur. The number of assignment, repair, and centre-update rounds is therefore at most $\left(\genfrac{}{}{0ex}{}{n-1}{K-1}\right)\le n^{K-1}$. Check stability after each update without an additional update round; for $K=1$, one update suffices.

For a finite dataset, alternate nearest-centre assignment and replacement of each centre by the centroid of its assigned observations. Keep the current assignment whenever an observation is tied between nearest centres. A changed assignment then strictly decreases the within-cluster sum of squared Euclidean distances; updating centres cannot increase it by the centroid sum-of-squares identity.

After each centre update, the centres are determined by the current partition of a set of observation indices. There are only finitely many such partitions, so a strictly improving sequence cannot revisit one and must stop. A convenient exact stopping test is to check after each update whether every observation is still assigned to a nearest centre. This proof is for algorithm termination; it does not guarantee a global minimum.

Empty clusters need an explicit convention. To retain exactly $K\le n$ nonempty clusters, transfer an observation from a cluster with at least two members to each empty cluster, making it a singleton centred at that observation. This cannot increase the objective: the transferred observation now has squared distance zero, and no other contribution changes before centre updating. A deterministic choice is an eligible observation farthest from its currently assigned centre, with ties resolved by index. After the first round, an empty cluster can arise only during a strictly improving reassignment, so these repairs preserve the finite-termination argument.

For two distinct centroids in a Euclidean space, equal squared Euclidean distances expand to the displayed affine hyperplane. It is their perpendicular bisector; each closed half-space consists of points at least as close to the centroid on that side. This proves weak linear separability after a two-centroid nearest-assignment step, allowing ties on the boundary. Coincident centroids are an essential exception: every point ties and the distance comparison supplies no nonzero normal vector.

For a nonempty finite collection of Euclidean vectors, its sample mean $\bar{x}=n^{-1}{\sum }_i{x}_i$ uniquely minimizes the sum of squared Euclidean distances to a proposed centroid $z$. Expand each squared Euclidean norm around $\bar{x}$ and use ${\sum }_i(x_i-\bar{x})=0$ to cancel the cross term. The displayed identity leaves a nonnegative term $n\Vert z-\bar{x}{\Vert }^2$, equal to zero exactly at $z=\bar{x}$.