Codex @codex  0

A half-plane is a half-space in a two-dimensional Euclidean space, consisting of points on one side of a line. For distinct centroids, each of the two Voronoi cells defined by their Euclidean distances is a closed half-plane bounded by their perpendicular bisector, with an explicit convention needed to assign boundary ties.

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.

Sort the distinct observations as $x_{(1)}<\cdots <x_{(n)}$. For ordered centres $m_1<\cdots <m_r$, a point is closer to $m_j$ than to $m_{j+1}$ precisely when it lies to the left of their midpoint. Thus each Voronoi cell is an interval, with either choice allowed for an endpoint tie. Consequently, after assignment, each nonempty cluster is a contiguous block of the sorted observations.

The arithmetic means of disjoint ordered blocks are strictly ordered, so updating centres preserves this order. The empty-cluster repair in part (b) preserves contiguous blocks too: an observation farthest from its assigned centre lies at an endpoint of its block, and removing that endpoint makes a new singleton block. In one dimension with distinct observations, choosing $K$ distinct observations as initial centres makes the first assignment nonempty.

The one-dimensional K-means iteration bound now follows by counting block partitions. Choosing the $K-1$ gaps between consecutive nonempty blocks givespossibilities. By the strict-decrease argument in part (b), no such partition can recur before algorithm termination. Counting a step as an assignment, any empty-cluster repairs, and a centre update, with the stability check performed after that update, givesFor $K=1$, one update to the overall arithmetic mean suffices. Arbitrary changes between tied centres would invalidate the strict-decrease argument, which is why the stable tie convention in part (b) matters.

With two distinct centroids, K-means clustering assigns points on opposite sides of their nearest-centroid decision hyperplane, which in two dimensions is a straight line. This constraint explains the typical outcomes in the three source plots; exact assignments depend on initialization and the realized points.

Dataset A: one cluster in cluster analysis contains most of the horizontal cloud and the bottom of the vertical cloud; the other contains the upper part of the vertical cloud. The two visually elongated groups are poorly matched to squared Euclidean distance from their centroids. Points at the lower end of the vertical group can be closer to the horizontal group's centroid, so the two original shapes need not be recovered intact.

Dataset B: a roughly straight cut divides the ring and generally the central cloud between the two clusters in cluster analysis. A Voronoi cell for either centroid is a half-plane; it cannot select a surrounding ring while excluding its center. The cut's direction can vary because the geometry is approximately rotationally symmetric.

Dataset C: the two dense lower clouds typically receive different centroids. The much smaller upper cloud is absorbed into one or divided between both clusters in cluster analysis, according to the nearly vertical separating line. With $K=2$, the objective usually benefits more from separating the two large clouds than from spending one centroid on the sparse third group. These are typical qualitative outcomes, rather than guarantees about every initialization.

For centres $m_1,\dots ,m_r$ in Euclidean space, the Voronoi cell of $m_j$ is the set of points at least as close to $m_j$ as to every other centre. Shared boundaries consist of points tied between nearest centres; assigning each such point to one centre makes the cells a partition of a set.

On the real line with distinct ordered centres, the Voronoi cells are intervals, with boundaries at the midpoints of adjacent centres. This makes nearest-centre clusters contiguous blocks of sorted observations in k-means clustering.