6.1. Definitions and Properties

6.1.1. Voronoi Diagram in 2D

We start with the discussion of the simple Voronoi diagram in the plane. Let S be a set of n ‰ 3 points p ₁ , p ₂ , , p _n in the plane with . In the following, we assume that the points are in general position , i. e., no four of them lie on the same circle and no three of them on the same line; see Section 9.5 for handling degenerate situations in geometric computing.

The Voronoi diagram in 2D is represented by a graph. Each face of the graph is dedicated to a unique point p _i . Note that the points are sometimes denoted as sites. The face of p _i represents all points in 2D that are closer to p _i than to any other p _j . The representation of the graph can be given by a double-connected edge list (DCEL); see Section 9.1. An example of a Voronoi diagram in 2D is shown in Figure 6.1.

Figure 6.1: The Voronoi diagram of a set of sites in the Euclidean plane.

Following the lines of [Okabe et al. 92] or [Aurenhammer and Klein 00], we define the Voronoi diagram more formally so that the concept can be easily generalized. For two points and , let d ( p _i , p _j ) denote their Euclidean distance. By B , we denote the closure of a set B . The closure of B also contains the points on the boundary of a given area; for example, the closure of an open interval ( a, b ) ˆˆ is given by [ a, b ].

Definition 6.1. (Voronoi diagram.) For p _i , p _j ˆˆ S let

denote the bisector of p _i and p _j . Bis( p _i , p _j ) represents the perpendicular line through the midpoint of the line segment p _i p _j . The bisector separates the plane into two open half-planes

and

where H( p _i , p _j ) contains p _i and H( p _j , p _i ) contains p _j .

The Voronoi region of p _i with respect to S is defined by the intersection of n ˆ 1 half-planes as follows :

The Voronoi diagram VD( S ) of S itself is defined by

By definition, the Voronoi diagram represents a graph. An illustration of the Voronoi diagram is given in Figure 6.1. It shows how the plane is decomposed by VD( S ) into open Voronoi regions . Let us discuss the graph structure more precisely. The boundary shared by two Voronoi regions belongs to the diagram and is called a Voronoi edge . For the Voronoi edge e bordering the regions of p _i and p _j , we easily conclude e Bis( p _i , p _j ), i.e., every Voronoi edge is part of a corresponding bisector. The endpoints of a Voronoi edge are called Voronoi vertices . A Voronoi vertex must belong to the common boundary of three Voronoi regions.

For every point p in the plane, we can uniquely determine its role within a Voronoi diagram of a set of sites S . We expand the circle Circle( p, r ) with center p and radius r by increasing r continuously. One of the following events will uniquely determine the role of point p in the Voronoi diagram:

If Circle( w, r ) first hits exactly one of the n sites, say p _i , then w ˆˆ VoR( p _i , S );
If Circle( w, r ) first hits exactly two sites p _i and p _j simultaneously , w belongs to the Voronoi edge of p _i and p _j ;
If Circle( w, r ) first hits exactly three sites p _i , p _j , and p _k simultaneously, w is the Voronoi vertex of p _i , p _j , and p _k .

The expanding circle characterization can be easily proven by the definition of the Voronoi diagram. Furthermore, we will enumerate the following three elementary properties of a Voronoi diagram:

Each Voronoi region VoR( p _i , S ) is the intersection of at most n ˆ 1 open half-planes containing the site p . Every VoR( p _i , S ) is open and convex. Different Voronoi regions are disjoint ;
A point p _i of S lies on the convex hull of S iff its Voronoi region VoR( p _i , S ) is unbounded;
The Voronoi diagram VD( S ) has O ( n ) many edges and vertices. The average number of edges in the boundary of a Voronoi region is less than 6.

Apart from the last fact, which needs an application of the Eulerian formula for planar graphs, see [Gibbons 85], the structural properties can be easily deduced from the definition of the Voronoi diagram and the convex hull. The Voronoi diagram is a simple linear structure and provides for a partition of the plane into cells of the same neighborship. We omit the proofs and refer to the surveys mentioned in the beginning; for example, see [Aurenhammer and Klein 00].

6.1.2. Delaunay Triangulation in 2D

We consider the dual graph of the Voronoi diagram, the so-called Delaunay triangulation . The dual graph dual( G ) of a geometric graph G is defined as follows. Every face F of G represents a vertex in dual( G ). Two faces that share a common edge in G build an edge in dual( G ). If G is the dual graph of G , G is called the primal graph of G , primal( G ) = G for short. Figure 6.2 shows an example of a graph and its dual. If the graph G is represented by a DCEL (see Section 9.1.1 and Section 9.1.2), one can easily build a DCEL for the graph dual( G ) in time O ( G ) using the primal DCEL. Note that the dual of the Voronoi diagram is given logically by a set of vertices and edges. In the following, we will consider a geometric interpretation that uses the sites as vertices.

Figure 6.2: The Voronoi diagram and the Delaunay triangulation of a set of sites in the Euclidean plane.

In general, a triangulation of a set S of points in the plane can be defined to be a planar graph with vertices from S and with a maximal number of edges so that all closed faces are triangles . The triangulation is convex if the complement of the outer face is convex. The edges adjacent to the outer face of the graph represent the convex hull of the point set. Since a triangulation T is a graph, it can be represented by a DCEL. The triangulation of a point set S has no more than O ( S ) triangles, which can be easily shown by induction, starting with a triangle. It is easy to see that a point set might have many triangulations. By simple induction starting with a single triangle, one can show that for a fixed point set S , every triangulation of S has the same number of triangles and edges.

Definition 6.2. (Delaunay triangulation.) For a set of sites S and the Voronoi diagram VD( S ), let every face be represented by its site. The Delaunay triangulation DT( S ) is the dual graph of the Voronoi diagram. The edges of DT( S )are called Delaunay edge s.

We will show that the Delaunay triangulation DT( S ) is in fact a triangulation if the set of sites (vertices) is in general position. An example is shown in Figure 6.2. We present two equivalent definitions of the Delaunay triangulation. They can be applied for the computation of the diagram and give rise also to generalizations . They are applicable for non-general situations, also.

Two points p _i , p _j of S build a Delaunay edge iff a circle C exists that passes through p _i and p _j and does not contain any other site of S in its interior or boundary.
Three points p _i , p _j , and p _k of S build a Delaunay triangle iff their circumcircle does not contain a point of S in its interior or boundary.

We will later concentrate on the last characterization of a Delaunay triangulation. It can be easily generalized and is highly recommended for construction schemes since we can make use of a simple incircle test and apply the paradigm of exact geometric computation; see also Chapter 9. We have to prove the following statements.

Lemma 6.3. Let S be a set of sites. Three points p _i , p _j , and p _k of S build a triangle in DT( S ) iff the circle passing through the endpoints of the triangle does not contain another point of S in its interior or boundary.

Two points p _i , p _j of S build a Delaunay edge in DT( S ) iff a circle C exists that passes through p _i and p _j and does not contain any other site of S in its interior or boundary.

A Delaunay triangulation is a convex triangulation iff no four points lie on a common circle; see Figure 6.2 .

Proof: The second part of the lemma can be proven as follows. If such a circle exists, the circumcenter c belongs to the boundary of the regions of p _i and p _j , and there is no other site in S that is closer to c . Therefore, a part of the bisector (including c ) belongs to VD( S ). Conversely, if p _i and p _j build a common edge that is part of the bisector of p _i and p _j , there is a point c on the bisector that is closer to p _i and p _j than to any other site. Then c is the circumcenter of the corresponding circle.

The first part of the lemma is proven as follows. If three Delaunay edges build a triangle for the points p _i , p _j , and p _k , the corresponding Voronoi edges share a common vertex v and exactly three Voronoi edges emanate from the vertex v ; otherwise , there is not a triangle between p _i , p _j , and p _k in the dual graph of the Voronoi diagram. The vertex v has the same distance to p _i , p _j , and p _k and is the circumcenter of the triangle ( p _i , p _j , p _k ). If the circumcenter of ( p _i , p _j , p _k ) contains another point p _l inside or on the boundary, then v will belong to VoR( p _l , S ), and the vertex v cannot be the unique Voronoi vertex of p _i , p _j , and p _k , which gives a contradiction. Therefore, a Delaunay triangulation fulfills the given property. The other way around, the circumcenter v of the triangle ( p _i , p _j , p _k ) exactly builds a Voronoi vertex in VD( S ), since no other point of S is closer to v than p _i , p _j , and p _k . The lines perpendicular to the edges of the triangle represent three bisectors of the corresponding points, and there are no other bisectors emanating from v . Starting at v , a part of each bisector has to belong to VD( S ), since v belongs to VD( S ). Therefore, the edges of ( p _i , p _j , p _k ) correspond to primal edges in VD( S ). Altogether, the triangle is a triangle in DT( S ), the dual of VD( S ).

Now, the last part of the lemma follows immediately. Every vertex of the Voronoi diagram represents exactly one triangle in the dual graph, which consists of triangles only.

The Delaunay triangulation has some interesting properties that are helpful in computer graphics applications.

For example, triangulations are often used for surface reconstructions. The chosen triangulation should not have small angles, which turn out to be more intractable. It can be shown that among all triangulations of S , the Delaunay triangulation has the best angle sequence. More precisely, for a triangulation T ( S ), we can insert all internal angles of the triangles in a vector T ( S ) _a by increasing order. It can be shown that T ( S ) _a < DT( S ) _a holds for all triangulations T ( S ) ‰ DT( S ). The minimal internal angle in DT( S ) is bigger than the minimal internal angle of every other triangulation. In other words, the Delaunay triangulation maximizes the minimal internal angle.

On the other hand, the Delaunay triangulation has some good graph properties. The Delaunay triangulation results in a graph of small graph-theoretical dilation; that is, for two vertices p _i and p _j in S , the ratio of the shortest graph distance over the shortest Euclidean distance of p _i and p _j is bounded by

which was shown in [Keil and Gutwin 89]. Therefore, the Delaunay triangulation results in a network of known quality. Note that the graph or triangulation with the lowest dilation might be different from DT( S ), which can be easily shown.

It can be shown also that the graph DT( S ) contains the minimum spanning tree of the given point set S . The minimum spanning tree is the shortest tree with respect to edge length that connects all sites p _i (see Section 7.1.3).