Fortune's Sweep is a sweepline algorithm for computing the Voronoi Diagram.
The input is a set of coordinates on the plane:
The following images are snapshots of the algorithm. The sweepline is the red line which is at the left side in the beginning:
A site event:
An intermediate position of the sweep line:
A circle event:
The complete Voronoi Diagram: