Graphics Reference
In-Depth Information
(2) An edge is orthogonal to the edge the Voronoi cells share but does not neces-
sarily intersect that edge.
(3) A Delaunay graph of a planar set is a planar graph.
(4) If no four points of
S
lie on a circle, then each face of the Delaunay cell
complex is a triangle.
(5) Three points of
S
are vertices of the same face of the Delaunay cell complex
if and only if the circle defined by them contains no point of
S
in its interior.
(6) Two points of
S
define an edge in the Delaunay graph if and only if there is a
closed disk that contains those points in its boundary and which contains no other
points of
S
.
(7) A Delaunay triangulation contains at most 3n - 6 edges and 2n - 4 faces.
Proof.
See [Aure91] or [BKOS97]. Parts (5), (6), and (7) follow from Theorem
17.7.2(3), (4), and (6).
Definition.
Let
S
be a finite set of points in
R
2
. A
triangulation of
S
is a simplicial
complex K whose vertex set is
S
and whose underlying space is the convex hull of
S
.
17.8.2 Theorem.
Let
S
be a finite set of points in the plane and let K be a trian-
gulation of
S
. Then K is the Delaunay triangulation of
S
if and only if the circle cir-
cumscribing any triangle in K does not contain any point of
S
in its interior.
Proof.
The theorem is an easy consequence of Theorem 17.8.1(5) and (6).
One of the important uses of Delaunay triangulations is to find a triangulation
of the convex hull of a set of points with the property that the triangles have as good
a shape as possible. For example, long thin triangles are undesirable in many
applications.
Definition.
Let
S
be a finite set of points in the plane and let K be a triangulation
of
S
. If K has m triangles and if we order the 3m angles q
i
of these triangles in increas-
ing order so that q
i
£q
j
if i < j, then the vector (q
1
,q
2
,...,q
3m
) is called an
angle vector
of K. The triangulation K is called
angle-optimal
for
S
if (q
1
,q
2
,...,q
3m
) ≥ (t
1
,t
2
,...,
t
3m
) for all angle vectors (t
1
,t
2
,...,t
3m
) of triangulations of
S
.
17.8.3
Theorem.
Let
S
be a finite set of points in the plane.
(1) Any angle-optimal triangulation of
S
is a Delaunay triangulation of
S
.
(2) Any Delaunay triangulation of
S
maximizes the minimal angle of the trian-
gles in any triangulation of
S
. If no four points of
S
lie on a circle, then the Delaunay
triangulation of
S
is angle-optimal.
Proof.
See [BKOS97].
The property in Theorem 17.8.3(2) can be expressed in another way. Note that
there are two ways that a quadrilateral can be triangulated because we can choose
either of the two diagonals. Given a triangulation, consider quadrilaterals that consist
of two adjacent triangles in that triangulation. A Delaunay triangulation has the
