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

Nancy M. Amato, Edgar A. Ramos

Research output: Contribution to conferencePaperpeer-review


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 R4 (the projection of certain polyhedra in R5) that runs in time O((n + f)log3 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(log2 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 R5, 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 in R3).

Original languageEnglish (US)
Number of pages10
StatePublished - 1996
Externally publishedYes
EventProceedings of the 1996 12th Annual Symposium on Computational Geometry - Philadelphia, PA, USA
Duration: May 24 1996May 26 1996


OtherProceedings of the 1996 12th Annual Symposium on Computational Geometry
CityPhiladelphia, PA, USA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'On computing Voronoi diagrams by divide-prune-and-conquer'. Together they form a unique fingerprint.

Cite this