A Sweepline Algorithm for Voronoi Diagrams

A geometric transformation is introduced that allows 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.