Two ways to watch a Voronoi diagram form
Growing cells. Imagine every site starts to grow a circle at the same instant and the same speed. Each location is claimed by whichever circle reaches it first — the nearest site. Where two circles meet, they stop, and the line where they touch is a Voronoi border. This is how crystal grains, cell colonies and many natural patterns end up looking like Voronoi diagrams.
Sweep line. Fortune's algorithm builds the same diagram by moving a horizontal line down the plane. For every site the line has passed, the algorithm keeps a parabola: the points equally far from the site and from the line. The lowest envelope of these parabolas, called the beach line, separates the part of the diagram that is already final (above) from the part that still depends on sites the line has not reached (below). As the line moves, the beach line traces out the Voronoi edges.
How to use the simulation
- Pick a mode and press Play, or drag the progress slider to scrub back and forth.
- Add, move or remove sites at any time; the animation updates immediately.
- Turn on Show the final diagram faintly to see where the borders will end up.
Why the sweep line matters
A naive Voronoi construction compares every site with every other, which slows down badly as the number of sites grows. Fortune's sweep line processes sites in order and only ever looks at neighbors on the beach line, finishing in O(n log n) time — the same order as sorting. Most practical libraries today instead build the Delaunay triangulation first (see the Delaunay generator) and read the Voronoi diagram off it, which has the same complexity. For the concepts behind both, read What is a Voronoi diagram?
Frequently asked questions
Why do growing circles make a Voronoi diagram?
If every seed starts growing at the same moment and at the same speed, a location is reached first by the nearest seed. Where two growth fronts meet, the location is equally far from both seeds — exactly a Voronoi border. Crystals, bacterial colonies and soap films form Voronoi-like patterns this way.
What is Fortune's algorithm?
Steven Fortune's 1986 sweep-line algorithm builds a Voronoi diagram in O(n log n) time. A line sweeps across the plane; above it, the part of the diagram that can no longer change is already final. The boundary of that finished part is the beach line, made of parabolic arcs, one per site.
What are the parabolas in the sweep view?
Each parabola is the set of points equally far from one site and from the sweep line. Points above a site's parabola are closer to that site than to anything still below the line, so their nearest site is already known. The lowest envelope of all parabolas — the beach line — is where the diagram is being drawn.
Does this page run the real event queue?
The animation shows the exact state of Fortune's algorithm at each position of the sweep line — the beach line and the finished part of the diagram — computed directly from the geometry. It does not list the individual site and circle events.