Civil Engineering Reference
In-Depth Information
3.5.3 Time complexity in the construction of DT
Based on a sound geometrical concept and the optimality properties, DT has important
applications in many fields, including data visualisation, terrain modelling, FE MG, sur-
face reconstruction and structural networking for arbitrary point sets. The popularity
of DT is attributed to its nice geometric properties as a dual of Voronoi tessellation and
the speed with which it can be constructed in two or higher dimensions. The existence,
uniqueness and other properties of DT have been studied for a long time as formal math-
ematical topics in computational geometry, and their computation issues and complexity
have been interesting problems for computer scientists. In view of its diverse applica-
tions, many strategies for its construction have been proposed. In a paper by Su and
Drysdale (1997), numerical tests on several DT algorithms, namely, divide-and-conquer,
sweep line algorithms, incremental algorithms, a fast incremental construction algorithm,
gift-wrapping algorithms and convex hull-based algorithms, were carried out, and their
performances were compared.
There are some estimates of the time complexity of DT in 2D and 3D, which could be
taken as a reference, but these asymptotic results may not be directly applicable to FE MG
as it only makes sense for very large n values, and the algorithm may not be available or
could not be easily implemented for practical use; and there are two more important steps
in FE MG relative to triangulation, namely, the generation of interior points and boundary
recover y.
The complexity of DT is very sensitive to the point distribution and the order of how
these points are processed. For instance, for DT in 3D, the estimated time complexity of
triangulating n points is
O
(n
4/3
) for the Bowyer's algorithm (Bowyer 1981) and higher for
the algorithms of Watson (1981) and Avis and Bhattacharya (1983). Joe (1989) presented
an algorithm that makes use of local transformations to construct a DT of a set of 3D
points. The empirical time complexity of the algorithm is
O
(n
4/3
), and
O
(n
2
) in the worst
case. Edelsbrunner et al. (1990) proposed a scheme in the worst case time of
O
(n
2
) for the
construction of 3D DT by projecting the given 3D points onto a paraboloid in four dimen-
sions. The convex hull of the 4D points on the paraboloid is constructed, and the 3D DT is
then obtained from an appropriate portion of the convex hull. Nevertheless, for practical
engineering applications with distance between points not greater than a ratio of, say, 1:10
6
,
DTs can be constructed in a virtually linear time complexity, as described in Chapter 8.
3.5.4 FE meshing by DT
By far, the most popular triangular MG schemes are based on the concept of DT (Cavendish
et al. 1985; Weatherill 1988; Lo 1989a; Joe 1991a,b,c; Wright and Jack 1994; Lewis et al.
1995; Escobar and Montenegro 1996; Krysl and Ortiz 2001; Nishioka et al. 2001; Quey
et al. 2011). The Delaunay criterion, also known as the empty-circle property, states that
any node must not be contained within the circumscribing circle of any triangle in the tri-
angulation, as shown in Figure 3.19. Although the Delaunay criterion has been known for
many years since the pioneer paper by Delaunay (1934), it was not until the work of Lawson
(1977), Bowyer (1981) and Watson (1981) that the criterion was exploited for developing
algorithms to form a convex hull of a given set of points. With the rapid development of the
FEM in the 1980s, the DT algorithm was further extended to generate valid FE meshes for
numerical analysis by Baker (1989a,b), George and Hermeline (1992), Ghosh and Mallett
(1994), Weatherill and Hassan (1994), Peterson et al. (1999) and others. For a comprehen-
sive view on the theoretical aspects of DT as well as its applications to FE MG, readers are
referred to the topic by George and Borouchaki (1998).
