A Sweepline Algorithm to Compute Voronoi Diagrams

Given a set of n sites, a Voronoi diagram is a collection of Voronoi cells, one cell for each given site, where each cell contains the points that are closest to that site. This lecture introduces a sweep line algorithm via the beach line construction. The beach line is the set of all parabolic arcs defined by the sites as foci and the sweep line as its common directrix. As the sweep line moves down, arcs appear or disappear from the beach line. We prove that new arcs can appear only at a new site. When arcs disappear, the center of the largest nonempty circle through three adjacent sites defines a vertex of the Voronoi diagram. With this beach line construction, we prove that all vertices of the Voronoi diagram are detected by circle events. The lecture ends by outlining the data structures and the main subroutines in the sweep line algorithm.