Delaunay triangulation, Voronoi tessellation,
Lawson's triangulation, the construction of
Thiessen or Dirichlet regions all denote the same
problem. This problem is so elementary that it can be found in
virtually every scientific and engineering discipline that uses
a conception of space.
Simply stated
,
the problem is as follows (note that the formulation is
independent of the spatial dimensionality).
The Delaunay graph (the Delaunay triangulation in the two-dimensional case) is easily obtained and closely related to the definition above.
From this definition one easily concludes that a
Delaunay triangle is formed between the three points
, 
, and 
if and only if the three Voronoi edges
(which are the perpendicular bisectors of the edges of the Delaunay
triangle) exist and hence
we obtain the following criterion:
and this 
is the circumcenter of the triangle
and 
is the radius of the circumcircle.
This means that the triangle is a Delaunay triangle if and only if
there is no other point 
of 
inside its circumcircle.
Speaking more intuitively, in the two-dimensional case the Voronoi regions are those areas where every point is closer to one of the grid points than to any other grid point. The (straight line) borders of the Voronoi regions are called Voronoi edges and are the set of points of equal distance to two nearest grid points. Every grid point lies within exactly one associated Voronoi region. Two grid points are next neighbors and are connected by a Delaunay edge when their Voronoi polygons touch each other, when they share a common Voronoi edge. The Voronoi edges are symmetry axes for next-neighbor grid point pairs.
Many different direct and indirect construction techniques for the Delaunay triangulation are available and it is beyond the scope of this section to give an extensive overview. A good introduction and explanation of the basic properties is given in [95].
The following nomenclature is adopted for describing the algorithms
and data structures in the subsequent sections.
A (directed) graph 
consists of
a set of nodes 
and
a set of edges 
,
, where an edge is an ordered
pair of nodes. The edge 
is said to be
incident to 
and the node is incident to 
. The
nodes and 
are then adjacent (via the edge ).
The edge 
is adjacent to , as and 
share the
common node .
The given points (the in Definition 6.3)
of the point cloud are called Delaunay
nodes, as they are the nodes of the Delaunay graph. The
Delaunay edges are the edges of the Delaunay graph and they
connect all Delaunay nodes.
Figure 6.1 shows a set of Delaunay nodes that are triangulated to form the Delaunay graph shown in Figure 6.2.
Figure 6.2: Delaunay graph for the grid point cloud
The Voronoi graph consists of Voronoi nodes (these are the
circumcenters of all Delaunay triangles) and Voronoi edges (these are
the sets of all 
that adhere to Equation 6.1). The
Voronoi graph of the point cloud in Figure 6.1 is shown in
Figure 6.3.
Figure 6.3: Voronoi graph for the grid point cloud
The following important dualities between the Voronoi graph and the Delaunay graph can be observed.
Table 6.1: Duality relations between Voronoi and Delaunay Graph
Note that in an unconstrained Voronoi tessellation, the boundary of the triangulated domain is always a convex polygon and the Delaunay nodes on the boundary correspond to open Voronoi polygons. Open Voronoi polygons contain two infinite Voronoi edges, which are dual to Delaunay boundary edges.
