Flip-based algorithm for Delaunay triangulation in expected or average-case O(nlogn)
The proof that edge flipping is expected to perform well goes back to this paper below as well as a couple related one around the same time-frame:

Guibas, Leonidas J., Donald E. Knuth, and Micha Sharir. "Randomized incremental construction of Delaunay and Voronoi diagrams." Algorithmica 7.1-6 (1992): 381-413.

A relatively concise algorithm and proof is given in the paper below by Edelsbrunner and Shah which describes a flip-based algorithm that runs in expected O(n log n) time.

Edelsbrunner, Herbert, and Nimish R. Shah. "Incremental topological flipping works for regular triangulations." Algorithmica 15.3 (1996): 223-241.

The algorithm involves adding points to the triangulation one at a time and using some history of the construction process to locate the new points. The paper is slightly more general, dealing with regular triangulations for which the Delaunay triangulation is a special case.