Theoretical analysis demonstrates O(n log n) sweepline computation of Voronoi diagrams for points, segments, and weighted sites, indicating optimal time and linear space efficiency.
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.
No takes yet. Share an insight, caveat, or question.
Steven Fortune (1986) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: