Focusing on the 2D plane:

Lawson's Flip Algorithm works in worst-case $O(n^2)$ flips. I have seen it mentioned that (other?) flip-based algorithms work in expected $O(nlogn)$ time for two dimensions. What is a simple example of an algorithm like this (perhaps with proof of complexity)? How would this be found?

Edit: If there are none in expected $O(nlogn)$, are there average-case $O(nlogn)$ flip-based algorithms?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.