342 VIII The Geometry of Numbers
4 Voronoi Cells
Throughout this section we supposeRnequipped with theEuclidean metric:
d(y,z)=‖y−z‖,where‖x‖=(xtx)^1 /^2. We call‖x‖^2 =xtxthesquare-normofxand we denote the
scalar productytzby(y,z).
Fix some pointx 0 ∈Rn. For any pointx =x 0 , the set of all points which are
equidistant fromx 0 andxis the hyperplaneHxwhich passes through the midpoint of
the segment joiningx 0 andxand is orthogonal to this segment. Analytically,Hxis the
set of ally∈Rnsuch that
(x−x 0 ,y)=(x−x 0 ,x+x 0 )/ 2 ,which simplifies to
2 (x−x 0 ,y)=‖x‖^2 −‖x 0 ‖^2.The set of all points which are closer tox 0 than toxis the open half-spaceGxconsist-
ing of all pointsy∈Rnsuch that
2 (x−x 0 ,y)<‖x‖^2 −‖x 0 ‖^2.The closed half-spaceG ̄x=Hx∪Gxis the set of all points at least as close tox 0 as tox.
LetXbe a subset ofRncontaining more than one point which isdiscrete,i.e.for
eachy∈Rnthere exists an open set containingywhich contains at most one point
ofX. It follows that each bounded subset ofRncontains only finitely many points of
Xsince, if there were infinitely many, they would have an accumulation point. Hence
for eachy∈Rnthere exists anx 0 ∈Xwhose distance fromyis minimal:
d(x 0 ,y)≤d(x,y) for everyx∈X. (1)For eachx 0 ∈ Xwe define itsVoronoi cell V(x 0 )to be the set of ally∈Rnfor
which (1) holds. Voronoi cells are also called ‘Dirichlet domains’, since they were
used by Dirichlet (1850) inR^2 before Voronoi (1908) used them inRn.
If we chooser>0 so that the open ball
βr(x 0 ):={y∈Rn:d(x 0 ,y)<r}contains no point ofXexceptx 0 ,thenβr/ 2 (x 0 )⊆V(x 0 ). Thusx 0 is an interior point
ofV(x 0 ).
Since
G ̄x={y∈Rn:d(x 0 ,y)≤d(x,y)},we haveV(x 0 )⊆G ̄xand actually
V(x 0 )= ∩
x∈X\x 0
G ̄x. (2)