Randomized incremental construction of Delaunay and Voronoi diagrams

Guibas, L. J. | Knuth, D. E. | Sharir, M.

Classics 

Algorithmica, 7, 381–413. See also 17th Int. Coll. on Automata, Languages and Programming, 1990, pp. 414–431.