A Sweepline Algorithm for Voronoi Diagrams + Code

We introduce a geometric transformation that allow Voronoi diagrams to be computed using 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.