On computing Voronoi diagrams by divide-prune-and-conquer

Using a divide, prune, and conquer approach based on geometric partitioning, we obtain: (1) An output sen-sitive algorithm for computing a weighted Voronoi dia-gram inR4 (the projection of certain polyhedra inR5) that runs in time O((n+ f) log3 f) where n is the num-ber of sites and f is the number of output cells; and (2) a deterministic parallel algorithm in the EREW PRAM model for computing an algebraic planar Voronoi dia-gram (in which bisectors between sites are simple curves consisting of a constant number of algebraic pieces of constant degree) that runs in time O(log2 n) using op-timal O(n logn) work. The first result implies an algo-rithm for the problems of computing the convex hull of a point set and the intersection of a set of halfspaces inR5, and computing the Euclidean Voronoi diagram in R4. The second result implies both sequential and parallel work-optimal deterministic algorithms for a number of Voronoi diagram problems (including line segments in the plane), and other non-Voronoi diagram problems that can fit in the framework (including the intersection of equal radius balls in R3 and some lower envelope problems inR3).