Page "Delaunay triangulation" Paragraph 34

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 v is added, we split in three the triangle that contains v, then we apply the flip algorithm.

Done naively, this will take O ( n ) time: we search through all the triangles to find the one that contains v, then we potentially flip away every triangle.

Then the overall runtime is O ( n < sup > 2 </ sup >).