Voronoi Regions And K-Means Cluster Boundaries

Why Centroid Boundaries Are Linear

Once a set of k-means centroids is fixed, every location in the feature space can be assigned to its nearest centroid using Euclidean distance. This rule does more than assign the observed data points: it partitions the whole space into regions. Understanding those regions makes the assignment step geometrically precise and gives a quick way to check which centroid is nearest without comparing every distance from scratch.

The key result is that the boundary between two distinct centroids is linear. In two dimensions it is a line; in three dimensions it is a plane. The result follows because the squared-distance expressions contain the same squared coordinates, which cancel when the distances are compared.

Definition: For fixed centroids $\mathbf{c}_1,\ldots,\mathbf{c}_K$ in Euclidean space, the Voronoi region of centroid $\mathbf{c}_k$ is the set of points at least as close to $\mathbf{c}_k$ as to every other centroid: $$ V_k=\{\mathbf{x}:\|\mathbf{x}-\mathbf{c}_k\|^2\leq \|\mathbf{x}-\mathbf{c}_j\|^2\text{ for every }j\}. $$ The use of $\leq$ includes ties, so a point on a boundary can belong to more than one region. A point has a unique nearest centroid when its distance to that centroid is strictly less than its distance to every other centroid.

Here $\mathbf{x}$ denotes a point in the feature space, and $\|\mathbf{x}-\mathbf{c}_k\|$ is the Euclidean distance from that point to centroid $k$. Squaring distances does not change their ordering because distances are nonnegative. In k-means, the centroids are the current centers used in the assignment step; the boundaries described here are for those centers held fixed.

Deriving a Pairwise Boundary

Consider two distinct centroids, $\mathbf{c}_a$ and $\mathbf{c}_b$. Their equal-distance boundary consists of points whose squared distances to the two centroids are equal. Expanding the squared norms gives

\|\mathbf{x}-\mathbf{c}_a\|^2=\|\mathbf{x}-\mathbf{c}_b\|^2

Using $\|\mathbf{x}-\mathbf{c}\|^2=\mathbf{x}^{T}\mathbf{x}-2\mathbf{x}^{T}\mathbf{c}+\mathbf{c}^{T}\mathbf{c}$, the common $\mathbf{x}^{T}\mathbf{x}$ terms cancel:

-2\mathbf{x}^{T}\mathbf{c}_a+\|\mathbf{c}_a\|^2 = -2\mathbf{x}^{T}\mathbf{c}_b+\|\mathbf{c}_b\|^2.

Rearranging yields the linear equation for the boundary. The same calculation with an inequality gives the half-space closer to either centroid.

2\mathbf{x}^{T}(\mathbf{c}_b-\mathbf{c}_a) = \|\mathbf{c}_b\|^2-\|\mathbf{c}_a\|^2

\|\mathbf{x}-\mathbf{c}_a\|^2\leq\|\mathbf{x}-\mathbf{c}_b\|^2 \quad\Longleftrightarrow\quad 2\mathbf{x}^{T}(\mathbf{c}_b-\mathbf{c}_a) \leq \|\mathbf{c}_b\|^2-\|\mathbf{c}_a\|^2.

This also explains the geometry. The coefficient vector $\mathbf{c}_b-\mathbf{c}_a$ is perpendicular to the boundary, so the boundary is a hyperplane in general dimension. The midpoint of the two centroids lies on it: substituting $\mathbf{x}=(\mathbf{c}_a+\mathbf{c}_b)/2$ into the equation gives equality. In two dimensions the hyperplane is a line, and in three dimensions it is a plane.

Worked Example: Boundary and Side for Two Planar Centroids

Suppose two current k-means centroids are $\mathbf{c}_1=(1,2)$ and $\mathbf{c}_2=(5,4)$. Find their equal-distance boundary, determine the side assigned to centroid 1, and classify the points $(2,3)$, $(4,1)$, and $(6,2)$.

Method. Write the squared-distance comparison, expand both sides, cancel the common quadratic terms, and then test each point against the resulting inequality.

For a point $(x,y)$, the boundary equation is

$$ (x-1)^2+(y-2)^2=(x-5)^2+(y-4)^2. $$

Expanding the left side gives $x^2-2x+1+y^2-4y+4$. Expanding the right side gives $x^2-10x+25+y^2-8y+16$. Cancel $x^2$ and $y^2$, then collect terms:

-2x-4y+5=-10x-8y+41 \quad\Longleftrightarrow\quad 8x+4y=36 \quad\Longleftrightarrow\quad 2x+y=9.

Centroid 1 is at least as close when its squared distance minus centroid 2’s squared distance is nonpositive. That difference is $8x+4y-36$, so the side for centroid 1 is $2x+y\leq 9$; the side for centroid 2 is $2x+y\geq 9$.

At $(2,3)$, $2x+y=4+3=7<9$, so centroid 1 is nearer. Checking the distances gives $\sqrt{(2-1)^2+(3-2)^2}=\sqrt{2}$ and $\sqrt{(2-5)^2+(3-4)^2}=\sqrt{10}$, consistent with the inequality.

At $(4,1)$, $2x+y=8+1=9$, so the point is on the boundary. Its squared distances are $3^2+(-1)^2=10$ and $(-1)^2+(-3)^2=10$, confirming a tie.

At $(6,2)$, $2x+y=12+2=14>9$, so centroid 2 is nearer. The squared distances are $5^2+0^2=25$ and $1^2+(-2)^2=5$, respectively. The calculations check both the side assignment and the boundary classification. The common mistake this method avoids is treating equality as a strict assignment: the boundary point is equally near both centroids.

A Region Is an Intersection of Half-Spaces

With more than two centroids, the region for one centroid must satisfy a comparison against every other centroid. Each comparison is a linear inequality, so the region is the intersection of the corresponding half-spaces. A candidate point belongs to the region only if it satisfies all of those inequalities.

V_k= \bigcap_{j\ne k} \left\{\mathbf{x}: 2\mathbf{x}^{T}(\mathbf{c}_j-\mathbf{c}_k) \leq \|\mathbf{c}_j\|^2-\|\mathbf{c}_k\|^2 \right\}.

For a finite set of distinct centroids, this describes closed regions that meet along their boundaries. Points strictly satisfying the comparison against every other centroid have a unique nearest centroid. Equality in one or more comparisons identifies a tie. If centroids are not distinct, the strict-comparison condition matters: two identical centroids have equal distance from every point, not just from points on a particular boundary.

Worked Example: Building One Region from Three Centroids

Let three centroids be $\mathbf{c}_1=(0,0)$, $\mathbf{c}_2=(4,0)$, and $\mathbf{c}_3=(2,4)$. Derive the region for centroid 1, then classify $(1,1)$ and $(1,3)$.

Method. Compare centroid 1 separately with centroids 2 and 3. The intersection of the two resulting half-planes is the region for centroid 1.

Against centroid 2, the squared-distance comparison is $x^2+y^2\leq(x-4)^2+y^2$. Cancel $x^2+y^2$ and simplify to $x\leq2$.

Against centroid 3, the comparison is $x^2+y^2\leq(x-2)^2+(y-4)^2$. Expanding the right side gives $x^2-4x+4+y^2-8y+16$. Cancelling the common squared terms and rearranging gives $4x+8y\leq20$, or $x+2y\leq5$. Therefore:

V_1=\{(x,y):x\leq2\text{ and }x+2y\leq5\}.

For $(1,1)$, the two left sides are $1$ and $1+2(1)=3$, satisfying both limits $2$ and $5$. It lies in $V_1$. Direct squared distances are $2$ to centroid 1, $10$ to centroid 2, and $10$ to centroid 3, so centroid 1 is uniquely nearest.

For $(1,3)$, the first condition holds because $1\leq2$, but the second fails because $1+2(3)=7>5$. Thus it is not in $V_1$. Its squared distances to centroids 1, 2, and 3 are $10$, $18$, and $2$, so centroid 3 is uniquely nearest. Checking all three distances confirms that satisfying just one of the two inequalities is not enough to belong to $V_1$.

Common Boundary Mistakes

A frequent algebra error is to compare distances but fail to square them consistently, or to expand only one side correctly. The safe procedure is to begin with squared distances, expand both sides, cancel the shared squared-coordinate terms, and check the direction of the inequality with a centroid itself.

For example, with centroids $(1,2)$ and $(5,4)$, an incorrect expansion might leave the boundary as $8x+4y=36$ but then declare the first centroid’s side to be $8x+4y\geq36$. That reverses the assignment. Substituting the first centroid $(1,2)$ gives $8(1)+4(2)=16<36$, so its side must be $8x+4y\leq36$. This test point is a simple check on the sign.

Another trap is claiming that every point in a region has a unique nearest centroid. Regions defined with $\leq$ include their boundaries, where ties occur. A precise claim of uniqueness requires strict distance inequalities against every other centroid. Also, if two centroids coincide, the distance to them is equal everywhere; the usual picture of two distinct sites separated by a single bisecting hyperplane does not apply to that pair.

Key takeaway: For fixed, distinct centroids, each pairwise nearest-centroid boundary is a perpendicular-bisector hyperplane. A centroid’s Voronoi region is the intersection of the half-spaces on its side of all pairwise boundaries. Keep boundary ties separate from strict, unique assignments.

Worked Example: A Three-Dimensional Boundary and Assignment

Suppose two centroids in a three-feature space are $\mathbf{c}_1=(2,1,0)$ and $\mathbf{c}_2=(-1,3,2)$. Find their boundary, identify the side nearest centroid 1, and assign $\mathbf{x}=(1,2,1)$.

Method. Use the vector boundary equation, then use the sign of the squared-distance difference to select the side and verify the assignment directly.

The centroid norms squared are $\|\mathbf{c}_1\|^2=2^2+1^2+0^2=5$ and $\|\mathbf{c}_2\|^2=(-1)^2+3^2+2^2=14$. The difference vector is $\mathbf{c}_2-\mathbf{c}_1=(-3,2,2)$. Therefore the boundary equation is

2(-3x+2y+2z)=14-5 \quad\Longleftrightarrow\quad -6x+4y+4z=9.

The side nearer centroid 1 satisfies $-6x+4y+4z\leq9$, from the squared-distance inequality with centroid 1 on the left. At $(1,2,1)$, the expression is $-6+8+4=6\leq9$, so centroid 1 is nearer. Directly, the squared distance to centroid 1 is $(1-2)^2+(2-1)^2+(1-0)^2=3$. The squared distance to centroid 2 is $(1+1)^2+(2-3)^2+(1-2)^2=6$. Since $3<6$, the point has a unique nearest centroid, as the inequality predicted. The boundary is a plane in this three-dimensional feature space.

Check Your Understanding

For each problem, derive or use the appropriate linear comparison and check whether the point is on a boundary when relevant.

Two planar centroids are $(1,0)$ and $(5,2)$. Find their boundary, state the half-plane for the first centroid, and classify $(2,2)$. (Answer: Boundary $2x+y=7$; first-centroid side $2x+y\leq7$; $(2,2)$ is uniquely nearest the first centroid.)
Two one-dimensional centroids are $-2$ and $4$. Find the boundary and identify the region for the centroid at $-2$. Which centroid is nearer to $x=0$? (Answer: Boundary $x=1$; the region for $-2$ is $x\leq1$; $x=0$ is uniquely nearest $-2$.)
Centroids are $(0,1)$ and $(4,3)$. Find the equal-distance line and decide which centroid is nearer to $(2,1)$. (Answer: Boundary $2x+y=6$; $(2,1)$ is uniquely nearest $(0,1)$.)
Three centroids are $(0,0)$, $(6,0)$, and $(0,4)$. Write the region for $(0,0)$ as two inequalities and classify $(2,1)$. (Answer: $x\leq3$ and $y\leq2$; $(2,1)$ is uniquely nearest $(0,0)$.)
Two listed centroids are both $(0,0)$, and a third is $(4,0)$. For the point $(1,0)$, is the nearest centroid unique? What is the equal-distance set between either duplicate centroid and $(4,0)$? (Answer: No; the point is equally distant from both duplicate centroids, and the equal-distance set between either duplicate and $(4,0)$ is the line $x=2$.)

What You'll Learn