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

Nancy M. Amato, Edgar A. Ramos

Research output: Contribution to conferencePaper

Abstract

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)
Pages166-175
Number of pages10
DOIs
StatePublished - 1996
Externally publishedYes
EventProceedings of the 1996 12th Annual Symposium on Computational Geometry - Philadelphia, PA, USA
Duration: May 24 1996May 26 1996

Other

OtherProceedings of the 1996 12th Annual Symposium on Computational Geometry
CityPhiladelphia, PA, USA
Period5/24/965/26/96

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

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

  • Cite this

    Amato, N. M., & Ramos, E. A. (1996). On computing Voronoi diagrams by divide-prune-and-conquer. 166-175. Paper presented at Proceedings of the 1996 12th Annual Symposium on Computational Geometry, Philadelphia, PA, USA, . https://doi.org/10.1145/237218.237347