PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
January 1, 1986336 citations

A sweepline algorithm for Voronoi diagrams

View Full Paper
SFSteven Fortune

Key Points

  • To introduce a geometric transformation that allows sweepline techniques to construct Voronoi diagrams simply and efficiently across various site types.
  • Formulated a geometric transformation adapting the plane-sweep paradigm to track advancing Voronoi boundary fronts.
  • Applied the transformation to construct algorithms for standard point sites, line segment sites, and weighted point sites.
  • Achieved an optimal worst-case time complexity of O(n log n) for all site variations.
  • Maintained a linear space complexity of O(n) across all diagram constructions.

Abstract

We present a transformation that can be used to compute Voronoi diagrams with a sweepline technique. The transformation is used to obtain simple algorithms for computing the Voronoi diagram of point sites, of line segment sites, and of weighted point sites. All algorithms have O(n log n) worst case running time and use O(n) space.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Steven Fortune (1986) studied this question.

synapsesocial.com/papers/6a01262ab124fe5819863f1bhttps://doi.org/10.1145/10515.10549
Ask AI
Helpful
Bookmark
Share
View Full Paper

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

  1. 1AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments1987 · 295 citations
  2. 2Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams1987 · 145 citations
  3. 3Computational Geometry--An Introduction.1986 · 4,277 citations
  4. 4Closest-point problems1975 · 1,068 citations
  5. 5Computing Dirichlet Tessellations in the Plane1978 · 722 citations