Number Theory: An Introduction to Mathematics

4 Voronoi Cells 343

It follows at once from (2) thatV(x 0 )is closed and convex. HenceV(x 0 )is the closure
of its nonempty interior.
According to the definitions of§3, the Voronoi cells form a tiling ofRn,since

Rn=∪

x∈X

V(x),

intV(x)∩intV(x′)=∅ ifx,x′∈Xandx=x′.

A subsetAof a convex setCis said to be afaceofCifAis convex and, for
anyc,c′∈C,(c,c′)∩A=∅impliesc,c′∈A. The tiling by Voronoi cells has the
additional property thatV(x)∩V(x′)is a face of bothV(x)andV(x′)ifx,x′∈X
andx =x′. We will prove this by showing that ify 1 ,y 2 are distinct points ofV(x)
and ifz∈(y 1 ,y 2 )∩V(x′),theny 1 ∈V(x′).
Sincez∈V(x)∩V(x′),wehaved(x,z)=d(x′,z). Thuszlies on the hyperplane
Hwhich passes through the midpoint of the segment joiningxandx′and is orthogo-
nal to this segment. Ify 1 ∈/V(x′),thend(x,y 1 )<d(x′,y 1 ). Thusy 1 lies in the open
half-spaceGassociated with the hyperplaneHwhich containsx.Buttheny 2 lies in
the open half-spaceG′which containsx′,i.e.d(x′,y 2 )<d(x,y 2 ), which contradicts
y 2 ∈V(x).
We now assume that the setXis not only discrete, but alsorelatively dense,i.e.

(†) there exists R > 0 such that, for eachy ∈ Rn,thereissomex ∈ X with
d(x,y)<R.

It follows at once thatV(x 0 )⊆βR(x 0 ). ThusV(x 0 )is bounded and, since it is
closed, even compact. The ballβ 2 R(x 0 )contains only finitely many pointsx 1 ,...,xm
ofXapart fromx 0. We are going to show that

V(x 0 )=

m

∩

i= 1

G ̄xi. (3)

By (2) we need only show that ify∈

⋂m
i= 1 G ̄xi,theny∈G ̄xfor everyx∈X.
Assume that d(x 0 ,y)≥Rand choosezon the segment joiningx 0 andyso that
d(x 0 ,z)=R.Forsomex∈Xwe have d(x,z)<Rand hence 0<d(x 0 ,x)< 2 R.
Consequentlyx=xifor somei∈{ 1 ,...,m}.Sinced(xi,z)<R=d(x 0 ,z),we
havez∈/G ̄xi. But this is a contradiction, sincex 0 ,y∈G ̄xiandzis on the segment
joining them.
We conclude that d(x 0 ,y)<R.Ifx∈Xandx=x 0 ,x 1 ,...,xm,then

d(x,y)≥d(x 0 ,x)−d(x 0 ,y)

≥ 2 R−R=R>d(x 0 ,y).

Consequentlyy∈G ̄xfor everyx∈X.
It follows from (3) thatV(x 0 )is a polyhedron. SinceV(x 0 )is bounded and has a
nonempty interior, it is actually ann-dimensional polytope.
The faces of a polytope are an important part of its structure. An (n− 1 )-
dimensional face of ann-dimensional polytope is said to be afacetand a 0-dimensional
face is said to be avertex. We now apply toV(x 0 )some properties common to all poly-
topes.