On parallel computation of Voronoi diagrams (Q1123595)

We present an \(O(\log^ 3n)\) algorithm for constructing the Voronoi diagrams of a set of n points on a shared memory parallel computer, where concurrent reads are allowed but no two processors can simultaneously attempts to write into the same memory location. If concurrent writes are allowed, the algorithm would run in \(O(\log^ 2n)\) time.