Editing Delaunay triangulation (section)

===Incremental===
The most straightforward way of efficiently computing the Delaunay triangulation is to repeatedly add one vertex at a time, retriangulating the affected parts of the graph.  When a vertex {{mvar|v}} is added, we split in three the triangle that contains {{mvar|v}}, then we apply the flip algorithm.  Done naïvely, this will take {{math|O(''n'')}} time: we search through all the triangles to find the one that contains {{mvar|v}}, then we potentially flip away every triangle.  Then the overall runtime is {{math|O(''n''<sup>2</sup>)}}.

If we insert vertices in random order, it turns out (by a somewhat intricate proof) that each insertion will flip, on average, only {{math|O(1)}} triangles – although sometimes it will flip many more.{{r|GKS1992}} This still leaves the point location time to improve.  We can store the history of the splits and flips performed: each triangle stores a pointer to the two or three triangles that replaced it.  To find the triangle that contains {{mvar|v}}, we start at a root triangle, and follow the pointer that points to a triangle that contains {{mvar|v}}, until we find a triangle that has not yet been replaced.  On average, this will also take {{math|O(log ''n'')}} time.  Over all vertices, then, this takes {{math|O(''n'' log ''n'')}} time.{{r|deBerg}}  While the technique extends to higher dimension (as proved by Edelsbrunner and Shah{{r|ES1996}}), the runtime can be exponential in the dimension even if the final Delaunay triangulation is small.

The [[Bowyer–Watson algorithm]] provides another approach for incremental construction.  It gives an alternative to edge flipping for computing the Delaunay triangles containing a newly inserted vertex.

Unfortunately the flipping-based algorithms are generally hard to parallelize, since adding some certain point (e.g. the center point of a wagon wheel) can lead to up to {{math|O(''n'')}} consecutive flips.  Blelloch et al.{{r|Parallel}} proposed another version of incremental algorithm based on rip-and-tent, which is practical and highly parallelized with polylogarithmic [[Analysis of parallel algorithms|span]].