Parallel computation of Voronoi diagrams


Ivan Stojmenović, Marija Kulaš




The paper presents algorithms for solving some computational geometry problems on a shared memory parallel computer, where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location. We present new $0(\log^3(n))$ time with $0(n\log(n))$ processors algorithm for construction of the Voronoi diagrams and show that the algorithm given in [1] for solving the same problem does not work correctly. Also, we make the convex hull algorithm described in [1] more efficient by omitting their last step which is superfluous due to a too weak lemma they have given.