Fortune's Sweep

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: