4.1 Voronoi cells and k-center

Motivation

A collection of representative points is useful only after specifying how the other observations relate to it. Assigning an observation to a nearest representative creates a clustering rule. In Euclidean space, the rule also creates geometric regions for possible observations that have not yet been measured. Voronoi cells describe those regions without testing every possible location separately.

Choosing the representatives is a second problem. The k-center objective controls the largest distance from an observation to its representative. This is appropriate when every observation needs a distance guarantee: a small average distance cannot compensate for one observation that remains very far from every centre. The geometry of nearest sites gives the assignments, while the maximum-distance objective determines which sites should be chosen.

Two kinds of ties arise. An observation can have several nearest sites, and a greedy selection step can have several farthest observations. A specified tie rule makes a computation reproducible. It does not change the minimum distance to a set or the maximum of those distances. Closed geometric cells retain the shared boundaries; a single-valued assignment chooses who owns a tied observation.

Definitions

Definition

Nearest sites and closed Voronoi cells

For distinct Euclidean sites $S=\{s_1,\ldots,s_k\}\subset\mathbb R^d$, define

$$V_i=\{x\in\mathbb R^d:\|x-s_i\|_2\le\|x-s_j\|_2,\ \forall j\}.$$

These are the closed Voronoi cells. They cover the space and can overlap on equal-distance boundaries. A single-valued assignment can choose the smallest site index among all nearest sites.

The cell is not restricted to observed data. Its intersection with a finite dataset gives the observations that may be assigned to that site. The open interiors of different cells are disjoint, but writing non-strict inequalities is useful because it retains all points on a boundary. Distinct sites matter: coincident sites would have identical distance functions and could share an entire region rather than only a boundary.

Definition

Metric k-center radius

Let $X$ be a nonempty finite subset of a metric space $(M,d)$, and let $1\le k\le|X|$. For a nonempty centre set $S$, define

$$d(x,S)=\min_{s\in S}d(x,s),\qquad R(X,S)=\max_{x\in X}d(x,S).$$

The k-center problem minimizes this radius using $k$ centres. One may restrict the centres to $X$, or compare them with centres elsewhere in $M$.

The metric is symmetric and satisfies the triangle inequality. Its choice is part of the problem. In particular, ordinary Euclidean distance is a metric, while its square is not generally a metric. The assignments can agree under these two quantities even though the mathematical approximation guarantees have different constants.

Theorem/proposition

Proposition

Euclidean Voronoi cells are intersections of halfspaces

The cell of $s_i$ can be written as

$$V_i=\bigcap_{j\ne i} \{x:2(s_j-s_i)^Tx\le\|s_j\|_2^2-\|s_i\|_2^2\}.$$

It is therefore a closed convex polyhedral region, which may be unbounded. The equality hyperplane for two sites is their perpendicular bisector.

Proposition

Empty circumcircles and the Delaunay dual

For at least three planar sites with no three collinear and no four cocircular, a triple forms a Delaunay triangle exactly when its circumcircle has no other site in its interior. Its circumcentre is the corresponding Voronoi vertex. Two sites joined by a Delaunay edge have Voronoi cells sharing an edge.

Theorem

Farthest-first selection gives a factor-two radius

Start with any $s_1\in X$. Repeatedly add an observation maximizing its distance to the currently selected centres until $k$ centres have been chosen. Let the resulting set be $S$. For any set $O$ of $k$ centres in the same metric space,

$$R(X,S)\le2R(X,O).$$

Consequently, when an optimal set exists, $R(X,S)\le2R^*$ for its optimal radius $R^*$. The selected centres themselves belong to $X$.

Proof sketch or proof idea

Squaring the two nonnegative Euclidean distances preserves their order. Expanding $\|x-s_i\|_2^2\le\|x-s_j\|_2^2$ cancels $x^Tx$ and gives the halfspace inequality. Intersections preserve both convexity and closedness. Convexity means that the straight segment between any two points in a cell also stays in that cell; it does not imply that the cell has finite area.

A circumcentre is equidistant from the three vertices of its triangle. Its circumcircle is empty precisely when no other site is closer to that centre. Thus it is a common nearest-site point for the three cells. Under the stated position assumptions exactly three cells meet there. Connecting their sites gives the dual triangle. This also explains why a fourth site inside the circle invalidates that triangle.

Under these assumptions, the dual triangles fill the convex hull of the sites, whereas the Voronoi cells cover the entire plane. A site on the hull has an unbounded cell, and a hull edge corresponds to an outward Voronoi ray. The two drawings therefore occupy different geometric objects: joining sites produces edges inside the hull, while their dual bisectors may extend far outside it. Sharing a single vertex is also different from sharing an edge. The adjacency rule uses a one-dimensional cell boundary, not just any common point of the two closed cells.

For the approximation proof, write $R=R(X,S)$ and suppose $R>0$. Add one more witness point $s_{k+1}$ farthest from $S$, without including it in the returned answer. During the greedy process the current radius never increases. Whenever a new site was selected, its distance from every earlier site was therefore at least the final radius $R$. Hence

$$d(s_i,s_j)\ge R\qquad(1\le i<j\le k+1).$$

Assign these $k+1$ points to nearest centres in $O$. By the pigeonhole principle, two share a centre $o$. If $r=R(X,O)$, the triangle inequality gives

$$R\le d(s_i,s_j)\le d(s_i,o)+d(o,s_j)\le2r.$$

That proves the result. When $R=0$, the inequality follows immediately. The argument works for any comparison set $O$, so it covers both data-restricted and ambient-space optimal centres. Every step uses an ordinary metric distance, including distances to comparison centres.

More explicitly, if $S_t$ is the first $t$ selected sites, their radii obey $R(X,S_1)\ge\cdots\ge R(X,S_k)$. The new site $s_j$ has minimum distance $R(X,S_{j-1})$ to the earlier sites. Each individual distance to an earlier site is at least that minimum. The same statement applies to the witness $s_{k+1}$, whose minimum distance is exactly $R$. A positive final radius ensures that this witness is distinct from every selected site. This is the separation fact needed by the pigeonhole argument; the greedy choices need not coincide with any of the comparison centres.

Worked examples

Worked example

Example 1: Compute three cells and an unbounded edge

Take sites $s_1=(0,0)$, $s_2=(4,0)$, and $s_3=(0,4)$. Writing a location as $(u,v)$, the halfspace formulas give

$$V_1=\{u\le2,\ v\le2\},\qquad V_2=\{u\ge2,\ v\le u\},\qquad V_3=\{v\ge2,\ u\le v\}.$$

For $(3,1)$, the three squared distances are $10$, $2$, and $18$, so the second site is uniquely nearest. At $(2,1)$ the first two squared distances both equal $5$ and the third equals $13$. The point belongs to both closed cells, while the smallest-index rule assigns it to site 1.

The common boundary of the first two cells is $\{(2,t):t\le2\}$, a downward ray. The other two edges are a leftward ray from $(2,2)$ and a northeast ray along $u=v$. The common vertex $(2,2)$ has squared distance $8$ from every site. The Delaunay dual is the triangle joining the three sites. Its circumcentre happens to lie on its hypotenuse; a Voronoi vertex need not lie in the triangle's interior.

Worked example

Example 2: A new site removes a formerly valid triangle

Add $s_4=(1,1)$ to the preceding sites. The old circumcircle has centre $(2,2)$ and squared radius $8$, but the new site's squared distance to its centre is only $2$. Thus the circle is no longer empty, the old triple is not a Delaunay triangle, and $(2,2)$ is not a common nearest-site vertex for that triple.

Consider instead the triangle with vertices $(0,0)$, $(4,0)$, and $(1,1)$. Its circumcentre must satisfy $u=2$ from the first pair and $u+v=1$ from the first and third, so it is $(2,-1)$ with squared radius $5$. The remaining site $(0,4)$ has squared distance $29$ to this centre. The circle is empty and the new triple is Delaunay. Checking equal distances to three sites is therefore only part of the calculation: all remaining sites determine whether the circumcentre is also a Voronoi vertex.

Worked example

Example 3: A greedy radius can attain the factor two

Use ordinary distance on the line, with $X=\{0,1,2,8,9,10\}$ and $k=2$. Starting at $0$, farthest-first selects $10$. The distances to the chosen set are

$$\begin{array}{c|rrrrrr} x&0&1&2&8&9&10\\ d(x,\{0,10\})&0&1&2&2&1&0 \end{array}$$

The greedy radius is $2$. Centres $1$ and $9$ cover every observation with radius $1$. No two-centre solution can have radius below $1$: the three observations $0$, $2$, and $10$ have pairwise distances at least $2$, so two of them must share a centre and the triangle inequality forces a radius of at least $1$. Therefore $R^*=1$, and the factor-two bound is attained. Both comparison centres are themselves observations, so the same conclusion holds when centres are restricted to the dataset.

Computing assignments and farthest-first centres

The following NumPy calculation maintains one nearest-centre distance per observation. Adding a centre can only reduce those distances, so the update uses an elementwise minimum. The array order resolves a farthest-point tie by choosing its first occurrence.

import numpy as np

X = np.array([0.0, 1.0, 2.0, 8.0, 9.0, 10.0])
k = 2
selected = [0]
nearest = np.abs(X - X[selected[0]])
for _ in range(1, k):
    j = int(np.argmax(nearest))
    selected.append(j)
    nearest = np.minimum(nearest, np.abs(X - X[j]))
centres = X[selected]
labels = np.argmin(np.abs(X[:, None] - centres[None, :]), axis=1)
print("centres:", centres.tolist())
print("labels:", labels.tolist())
print("radius:", float(nearest.max()))

centres: [0.0, 10.0]
labels: [0, 0, 0, 1, 1, 1]
radius: 2.0

For observations in $\mathbb R^d$, replace the absolute differences by Euclidean norms of row differences. Maintaining the distances requires $O(n)$ storage and $O(nkd)$ arithmetic for direct Euclidean calculations. A single nearest-site query requires comparing distances to the sites; a Voronoi diagram instead records how all such answers vary over the ambient space. These serve different computational purposes.

Farthest-first also provides a useful record of progressively smaller covering radii. It is the current maximum of nearest-centre distances that matters, not the largest distance to any single centre. A point may be far from one centre and already be perfectly represented by another. Selecting by the latter quantity would spend centres without following the proved rule.

The radius guarantee concerns the finite observations in $X$. It does not bound all locations in an unbounded Voronoi cell: those locations can move arbitrarily far from its site. The cells explain the assignment rule for possible observations, while the computed radius certifies the distances of the supplied dataset. Keeping the domain of the maximum explicit prevents these two uses of nearest-site geometry from being confused.

Changing feature units can change that geometry. For a query at $(0,0)$ and sites $(0,3)$ and $(2,0)$, the second site is nearest under Euclidean distance. Doubling the first coordinate changes the sites to $(0,3)$ and $(4,0)$ and makes the first site nearest. A common scaling of every coordinate instead multiplies all distances and radii by the same factor. The approximation ratio survives that common scaling, while separate coordinate scalings define a different distance model in the original coordinates.

Common mistakes

Common mistake

Using geometric conclusions without their hypotheses

Voronoi edges may be finite segments, rays, or, for two sites, a complete bisector line. Boundary cells are often unbounded. The planar Delaunay triangle correspondence uses the stated general-position conditions; four cocircular sites can produce a vertex shared by four cells and a non-unique triangulation.

The halfspace derivation uses the Euclidean squared-norm expansion. Different metrics can give differently shaped cells, so the Euclidean bisector formula is not a general metric identity. The farthest-first guarantee is more general geometrically but needs the metric triangle inequality. Squaring Euclidean distances preserves the greedy order, yet changes a factor-two radius bound into a factor-four bound for the squared radius.

Summary

Nearest-site geometry turns pairwise distance comparisons into convex Euclidean regions, with tied boundaries kept in their closed cells. Empty circumcircles identify the corresponding Delaunay triangles. For metric k-center clustering, farthest-first selection creates separated witness points. The pigeonhole principle and triangle inequality then compare its largest assignment distance with any optimal radius.

Exercises

Checkpoint

Exercise 1: For sites $(0,0)$ and $(6,0)$, derive the closed cells. Where does $(3,5)$ lie, and how does the smallest-index rule assign it?

Expand the squared-distance inequality and keep its equality case.

Checkpoint

Exercise 2: Four sites are $(0,0)$, $(2,0)$, $(2,2)$, and $(0,2)$. Find their common equal-distance point and explain which general-position condition fails.

Compute the squared distance from the centre of the square to each vertex.

Checkpoint

Exercise 3: Run farthest-first for $X=\{0,2,3,9\}$, $k=2$, starting at $3$. Find the chosen sites and final radius.

After adding the farthest point, update every observation's nearest distance.

Checkpoint

Exercise 4: In Example 3, report the maximum squared assignment distance for the greedy and optimal centres. What ratio results, and why is a metric proof not applied directly to squared Euclidean distance?

Square both radii and test the triangle inequality on $0$, $1$, and $2$.

Solutions

Solution · Exercise 1 solution

The cells are $u\le3$ and $u\ge3$, with a full vertical line as their common boundary. Point $(3,5)$ belongs to both cells. Its two squared distances equal $34$, and the smallest-index rule assigns it to the first site.

Solution · Exercise 2 solution

The point is $(1,1)$, with squared distance $2$ to each site. All four sites lie on the same circle, so the no-four-cocircular condition fails. Four cells meet at this vertex; either diagonal can be used to triangulate the square.

Solution · Exercise 3 solution

The distances from $3$ are $3$, $1$, $0$, and $6$, so the next site is $9$. The nearest distances to $\{3,9\}$ are $3$, $1$, $0$, and $0$. The final radius is $3$.

Solution · Exercise 4 solution

The two maximum squared distances are $4$ and $1$, giving ratio $4$. Squared Euclidean distance fails the triangle inequality because $(2-0)^2=4>(1-0)^2+(2-1)^2=2$. The metric theorem applies to the ordinary radii; squaring its conclusion gives the factor-four statement for their squares.

Related notes

Centre objectives and Lloyd updates changes the clustering objective and updates the centres. SVD and principal components uses another squared-distance objective to choose a lower-dimensional representation. The course reading list collects further reading.