5.3.4 Incremental Search

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 $P$ 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 $P$. 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.