Constructing the Voronoi diagram of a set of line segments in parallel

In this paper we give a parallel algorithm for constructing the Voronoi diagram of a polygonal scene, i.e., a set of line segments in the plane such that no two segments intersect except possible at their endpoints. Our algorithm runs in O(log²(n)) time using O(n) processors in the CREW PRAM model.