** Next:** 5.3.5 Convex Hull
**Up:** 5.3 Algorithms for Constructing
** Previous:** 5.3.3 Incremental Construction

Starting with an initial Delaunay edge the Delaunay Triangulation is
incrementally constructed by attaching triangles to the current boundary of
the triangulation. The search for the correct point to be linked
to the current edge so that the circumcircle of the resulting triangle
contains no other points constitutes the main factor in the overall
performance of the algorithm.
From an initial edge the triangulation grows until the convex hull of the
point set is triangulated.
It can be observed that the growing boundary of the incomplete
triangulation forms an advancing front. Nevertheless, one must be aware of
the differences between an advancing front meshing method as described in
Section 4.4 and an advancing front style triangulation
algorithm [106,104] for a given point set .
The incremental search algorithm appears to originate from [63]
and [179].
It forms the foundation of the modified advancing front algorithm for
constraining boundaries which will be discussed in detail in
Section 6.4.

*Peter Fleischmann *

2000-01-20