This algorithm starts with constructing any triangulation. Then, the idea is to flip all non-locally Delaunay edges in this triangulation to be locally Delaunay. The concept of local Delaunayhood is discussed in [5] and [7]. A triangulation is Delaunay if and only if all edges are locally Delaunay. Algorithm uses a stack to keep all non-locally Delaunay edges. The stack contains at most one copy per edge and only the edges of the current triangulation. Following algorithm is due Charles Lawson and given in [5].
. Construct an arbitrary triangulation T of point set S.
. Push all non-locally interior edges of T on stack and mark them.
. While stack is non-empty do
= pop()
unmark 
if 
is non-locally Delaunay then
Replace 
by the edge connecting the respective
third vertices of the two incident triangles
Push other four edges of the two triangles into the stack if unmarked