Civil Engineering Reference
In-Depth Information
to every point in the set. A triangulation of a set of points is called the DT of the point set if
every triangle in the triangulation is a Delaunay triangle, as shown in Figure 3.19. The idea
of DT is very general, which can be easily extended to higher dimensions. For instance, the
DT in 3D is given by replacing the triangle by a tetrahedron, the circle by a sphere and the 2D
plane by a 3D space. The following lemma provides the basis for many algorithms in the
construction and verification of DT.
Lemma 3.1: Lemma of Delaunay
Let
T
(
S
) be a triangulation of the point set
S
. The necessary and sufficient condition that no
point of
S
is contained in the circumcircle of any triangle in the triangulation is that any two
adjacent triangles in the triangulation are Delaunay with respect to each other's vertices.
The lemma of Delaunay, as depicted in Figure 3.20, is also valid in higher dimensions sim-
ply by changing some of the terms in the relevant dimensions. To arrive at an efficient and
robust DT scheme, the fundamentals of DT and its implementation must be reviewed. Su
and Drysdale (1997) presented a comparison of sequential DT algorithms, including divide-
and-conquer, sweep line algorithm, incremental algorithm, fast incremental construction
algorithm, gift-wrapping algorithm and convex hull-based algorithm. Based on the numeri-
cal tests on SPARCstation 2 and DEC Alpha machines, it was reported that Dwyer's divide-
and-conquer algorithm (Dwyer 1987) was the
strongest
overall and was the most resistant
to bad data distribution with
O
(nlogn) as the worst case.
Although the end result of DT of a set of n distinct points is independent of the order fol-
lowing which the points are processed, the speed or the complexity of triangulation is very
sensitive to the order of how the points are processed. The divide-and-conquer algorithm is
robust as some sorting mechanism is already built into the algorithm, such that the data set
is always divided more or less into two equal portions. As for the insertion algorithm, for
randomly generated points, the complexity can vary from
O
(n) to
O
(n
2
) depending on the
order of point insertion. For the 2D DT of 1 million points on a PC, if points are inserted
following the natural order of point generation, triangulation time increases in a quadratic
manner with the number of points inserted, as shown in Figure 3.21. However, as also
shown in Figure 3.21, if points are sorted into cells, each of which is assigned more or less an
equal number of points, a linear time relationship of the same set of points is resulted if cells
of points are inserted one by one in a contiguous manner following the natural structural
layout of the cells. For a 2D triangulation of 1 million points,
O
(n
2
) complexity (149.5 s)
represents more than 125 times of an
O
(n) scheme (1.18 s), and this quasi-linear complexity
(a)
(b)
Figure 3.20
(a) Delaunay and (b) non-Delaunay triangulations.
