Before the implementation of the quadtree-based divide-and-conquer method, the use of an iterative scheme that constructs the Delaunay graph directly (not via the Voronoi graph like Algorithm 6.8) has been evaluated. It is intrinsically stable and requires less effort for the numerical detection of degeneracies than the divide-and conquer approach.
Figure 6.24 shows a snapshot of a triangulation performed by the iterative algorithm. The continuous lines are already existing Delaunay triangles. The algorithm maintains a list of all edges that are not yet occupied by two triangles and for each of these edges determines a node (from the given point cloud) that augments the current edge to a Delaunay triangle. The criterion is, of course, that no other node lies inside the circumcircle of the triangle. In Figure 6.24 the current edge of the iteration is the bold solid line and the two new edges created by triangulating the current edge with the augmenting Delaunay node are the bold dashed lines. The algorithm starts with initial edges which are the refined boundary edges (Section 6.4) or the two closest Delaunay points, in case no boundary is specified.
Figure 6.24: Iterative method for the direct construction of
the Delaunay graph
The only disadvantage of the iterative
method is that the implementation used only an array of the nodes sorted by
X-coordinates to accelerate the search of nodes in the vicinity on an
already existing edge. Hence the complexity was 
.
The iterative method can, however, also profitably use a quadtree for
the search for triangulation candidate nodes, in a similar manner as
the boundary refinement step, to achieve 
complexity.
The most intriguing feature of the iterative scheme is that it is, in
principle, applicable to three-dimensional problems as well.
The applicability of the divide-and-conquer scheme to three-dimensional problems is still under dispute. Although there is no obvious theoretical reason why the divide-and-conquer approach should fail in the three-dimensional case, practical implementation difficulties, especially for the merge step, may be anticipated. The iterative scheme, on the other hand, is prone to a straightforward implementation for arbitrary dimensions, provided that the maintenance of data structures equivalent to the DCEL can be implemented efficiently.