Graphics Reference
In-Depth Information
Figure 17.14.
A Voronoi diagram.
Figure 17.14 shows a Voronoi diagram for six sites. Here are a few basic facts
about the sets V(
p
):
17.7.1
Proposition.
Let
S
be a finite set of n points in the plane.
(1) Each V(
p
) is a nonempty convex set because it is an intersection of (convex)
halfplanes that contain
p
. It has a nonempty interior because it contains a small neigh-
borhood about
p
consisting of points that belong to no other Voronoi cell.
(2) The boundary of each V(
p
) is the union of at most n - 1 segments or halflines,
called the
edges
of V(
p
). (We assume that an edge is a maximal linear subset of the
boundary, that is, the lines determined by the edges are distinct, or, alternatively, no
two edges lie in the intersection of the same pair of Voronoi cells.) The boundary has
at most n - 1 vertices, where a
vertex
is the intersection of two edges.
(3) Each point in the interior of an edge of a V(
p
) is equidistant to
precisely
two
sites. Each vertex is equidistant to at least three sites.
(4) If
p
π
q
, then V(
p
) « V(
q
) is either empty or consists of a single edge.
(5) Every point of the plane belongs to at least one Voronoi cell V(
p
).
Proof.
Easy. See [Aure91] or [BKOS97].
Definition.
The
Voronoi diagram of the set
S
, denoted by Vor(
S
), is the set of Voronoi
cells V(
p
),
p
Œ
S
, together with their edges and vertices.
Proposition 17.7.1(4) and (5) imply that Vor(
S
) defines a kind of partition of the
plane. The only reason that we cannot call it a cell complex is that it contains
unbounded sets that are homeomorphic to half-open disks. (Cell complexes are defined
in Section 7.2.4 in [AgoM05]. Their cells must be homeomorphic to closed disks.)
Definition.
Given a point
p
, let C
S
(
p
) denote the largest circle centered at
p
that con-
tains no site of
S
in its interior.
17.7.2
Proposition.
Let
S
be a finite set of n points in the plane.
(1) Vor(
S
) contains precisely n “2-cells.”
(2) The Voronoi diagram contains no vertices if and only if all sites are collinear.
