A wavefront is composed of the minimum of parabolas formed by sites and a sweep line. Any point on a parabola is equidistant from the site and the sweep line.

As we sweep a line to create the Voronoi diagram, we maintain the invariant that every point already surpassed by the wavefront is known to belong to a specific Voronoi region.

Some Basics

• To create a Voronoi diagram, we start with a list of sites
• Each Voronoi region is associated with a site
• At each step of the sweep, our wavefront is determined by a set of arcs, which are parabolas defined by sites
• We add an arc to the wavefront when we encounter a new site with our sweep line
  • This is called a Site Event
• We delete an arc when its two adjacent arcs intersect, creating a Voronoi vertex
  • This is called a Circle Event
• Events are handled in order of priority where the highest priority event is the event the sweep line will encounter next

Parabola Math

A parabola in the wavefront is generated by a site, which is the focus, and the position of the sweep line, which is the directrix. As the sweep line moves past a site, the parabolic arc associated with that site changes.

Voronoi Diagrams

After the sweep line surpasses all events, all edges for Voronoi regions have been drawn. In the Voronoi diagram for sites [(0, 0), (0, 5), (4, 3)], all red points are closer to site (0, 0) than any of the other sites. All orange points are closest to site (4, 3) and all green points are closest to site (0, 5).

The edges of the regions, which were created by intersecting parabolas, are points equidistant to the sites on either side of the edge. A Voronoi vertex, which was created by the center of a circle defined by three points, is equidistant to the three sites it bounds.

A Voronoi region is unbounded if and only if its site lies on the convex hull of the sites.

Next →