Graphics Reference
In-Depth Information
Figure 17.15.
Characterizing vertices and edges of a
Voronoi diagram.
(3) A point
v
is a vertex of Vor(
S
) if and only if C
S
(
v
) passes through at least three
sites in
S
. See Figure 17.15.
(4) Two Voronoi cells V(
p
) and V(
q
) determine an edge of Vor(
S
) if and only if
there is a point
r
so that C
S
(
r
) contains
p
and
q
in its boundary but no other site. See
Figure 17.15.
(5) If no four points of
S
lie on a circle, then every vertex of Vor(
S
) belongs to
precisely three edges of Vor(
S
).
(6) Vor(
S
) contains at most 3n - 6 edges and at most 2n - 5 vertices.
Proof.
See [BKOS97]. (3) and (4) characterize the vertices and edges of Vor(
S
).
Next, we consider the question of how to compute the Voronoi diagram for n sites
efficiently. Because the problem of sorting n numbers can be reduced to computing a
Voronoi diagram, one should not expect any algorithm to be faster than O(n log n).
Fortune's algorithm ([Fort87]) is an algorithm that achieves this best complexity.
17.7.3 Theorem.
The Voronoi diagram of a set of n points in the plane can be
computed in time O(n log n) using O(n) space.
Proof.
See [BKOS97].
Voronoi diagrams can be generalized to higher dimensions. It has been shown
that Voronoi diagrams for n sites in
R
m
can be computed in O(n log n + n
Èm/2˘
) optimal
time. The important special case of Voronoi diagrams for three-dimensional linear
polyhedra has been studied extensively. A recent algorithm and implementation is
described in [EtzR99]. It separates the problem into two parts. First, a symbolic rep-
resentation called the
Voronoi graph
is computed and then the geometric part, namely,
the actual vertices and edges.
17.8
Delaunay Triangulations
Closely related to Voronoi diagrams are Delaunay triangulations. Again we shall
restrict ourselves to subsets of the plane.
