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 sensitive algorithm for computing a weighted Voronoi diagram in R⁴ (the projection of certain polyhedra in R⁵) that runs in time O((n + f)log³ f) where n is the number 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 diagram (in which bisectors between sites are simple curves consisting of a constant number of algebraic pieces of constant degree) that runs in time O(log² n) using optimal O(n log n) work. The first result implies an algorithm for the problems of computing the convex hull of a point set and the intersection of a set of halfspaces in R⁵, and computing the Euclidean Voronoi diagram in R⁴. 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 R³ and some lower envelope problems in R³).