The ninth Geometry entry, and a direct follow-up to Voronoi Diagram, which named this page in its own
Complexity section and left it unbuilt. That page builds each cell independently by intersecting
half-planes — O(n³) — or, cheaper, reads the diagram off an already-built Delaunay Triangulation. Fortune's algorithm skips
Delaunay entirely and builds the Voronoi diagram directly in O(n log n),
by sweeping an imaginary horizontal line down the plane and maintaining, at every position, the
boundary between the region already fully decided and the region that isn't yet.
That boundary is called the beach line: a chain of parabolic arcs, one per site whose region has started to matter, each arc the set of points exactly as close to its site as to the sweep line itself. A point strictly above the beach line already knows its nearest site for certain — no site below the sweep line could possibly be closer, since the sweep line itself is already farther away than the known nearest site is. A point on or below the beach line is still undecided. As the sweep line moves down, arcs grow, shrink, and vanish, and the breakpoints between adjacent arcs trace out the actual edges of the Voronoi diagram in real time — the diagram isn't computed at the end and then drawn; it's built stroke by stroke as the sweep passes.
The same 8 points, in the same order, as the Delaunay Triangulation and Voronoi Diagram demos. Step through the sweep and watch
the beach line (the jagged curve) grow new arcs at site events and lose them at
circle events — every circle event this demo fires is a real Voronoi vertex, and the
full set this algorithm finds matches, coordinate for coordinate, the 8 circumcenters the half-plane
Voronoi page's own dual-graph check already found independently — including that page's own verified
pitfall vertex at (−70, 50), off the canvas entirely.
Every arc on the beach line belongs to exactly one site, and its shape at any moment is fixed: the set of points equidistant from that site (its focus) and the sweep line (its directrix) — the textbook definition of a parabola. Two neighboring arcs' shared boundary, the breakpoint between them, is a point equidistant from both sites and the sweep line at once — which makes it equidistant from the two sites alone, since the sweep-line term cancels. That's exactly the perpendicular-bisector condition a Voronoi edge is built from. As the sweep line moves, this equidistance condition still holds continuously, so the breakpoint keeps tracing — and it turns out to trace a perfectly straight line, the actual bisector, the whole way: solving "where do these two sites' arcs currently meet" at any two different sweep positions gives two points on the same straight line, never a curve.
An arc vanishes when it narrows to nothing — the moment its left and right breakpoints meet. That happens exactly when three sites' arcs (the vanishing one and its two neighbors) become momentarily equidistant from a single point that's also equidistant from the sweep line: a circle through the three sites, tangent to the sweep line from above. The instant the sweep line reaches that circle's lowest point, the circle's center is simultaneously the point where the two outer breakpoints collide — a new Voronoi vertex — and the point where no other site can be closer (the circle is empty by construction, since the sweep line hasn't reached anything closer yet). This is a circle event, and it's scheduled the moment three arcs first become consecutive, not discovered by scanning — the same "only check what just became adjacent" discipline Bentley–Ottmann Algorithm uses for segment crossings, applied here to arc triples instead of segment pairs. A scheduled circle event can go stale if something changes the beach line before the sweep reaches it (a new site arriving in between, say) — this demo's own event log calls these out by name when they're skipped.
Simplified: a plain array walk stands in for a balanced-tree beach line (see Complexity), and the
event queue is a sorted array re-sorted on insert rather than a binary heap. circumcenter
is the same function this site's Delaunay and Voronoi pages already use.
// Breakpoint x between arc `l` (left) and arc `r` (right) at sweep position `d`.
function breakpointX(l, r, d) {
if (l.y === r.y) return (l.x + r.x) / 2; // equal-y sites: vertical bisector
const dl = 2 * (l.y - d), dr = 2 * (r.y - d);
const a1 = 1 / dl, b1 = -2 * l.x / dl, c1 = d + dl / 4 + l.x * l.x / dl;
const a2 = 1 / dr, b2 = -2 * r.x / dr, c2 = d + dr / 4 + r.x * r.x / dr;
const a = a1 - a2, b = b1 - b2, c = c1 - c2;
const sq = Math.sqrt(b * b - 4 * a * c);
const x1 = (-b + sq) / (2 * a), x2 = (-b - sq) / (2 * a);
return l.y < r.y ? Math.min(x1, x2) : Math.max(x1, x2);
}
// Does arc `b`, with left neighbor `a` and right neighbor `c`, converge to a circle event?
function checkCircleEvent(a, b, c) {
const cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
if (cross <= 0) return null; // not converging
const center = circumcenter(a, b, c);
const eventY = center.y + dist(center, b); // circle's bottom edge — when it fires
return { center, eventY };
}
// Main loop, sketched: pop the next event by y, then x.
while (events.length) {
const evt = events.shift();
if (evt.type === 'circle' && !evt.valid) continue; // stale — a neighbor changed since
if (evt.type === 'site') {
const above = findArcAbove(evt.site.x, evt.y); // walk the beach line
splitArc(above, evt.site); // one arc becomes three
checkNewCircleEvents(); // only the two freshly-changed triples
} else {
recordVertex(evt.center);
removeArc(evt.arc); // the vanishing arc's two neighbors meet
checkNewCircleEvents();
}
}Sites that tie exactly on the sweep's y-coordinate need their own case, not the general split. The general rule assumes the arc a new site lands on has had time to develop real width — but if a new site shares its y-coordinate with the arc directly above it, the sweep hasn't moved past that site at all yet, so the "arc" is a single point with zero width. Splitting a zero-width arc into three the normal way creates a spurious extra copy of that site's arc wedged between two other arcs it should never separate — a copy that can never converge to a real circle event (its own three-site test is permanently degenerate, since all the tied sites are collinear by construction), so it sits on the beach line forever, silently discarding whatever real vertex should have formed on either side of it. Verified with a 6,300-trial suite (random point sets, plus batches deliberately forcing exact y-ties, cocircular clusters, and collinear rows) cross-checked against this site's own Delaunay-triangulation circumcenters as an independent oracle: 149 of 6,300 trials (2.4%) produced the wrong vertex set before this fix — every single failure in a configuration with a tied or collinear y — reduced to 0 of 6,300 by handling the tie as a direct two-way insert (no duplicate arc) instead of the usual three-way split.
Splitting an arc has to hand its outer edges to the two new copies, not just wire up the two new inner ones. When a site event splits an existing arc into a left copy, the new site's arc, and a right copy, it's tempting to only build the two brand-new edges between them and leave it there. But the left copy's own left edge — its boundary with whatever arc was already beside it — still exists and still needs to reach a future vertex; if the split doesn't hand that edge reference to the new left-copy node, nothing on the beach line points to it anymore, and it can never be closed off by the circle event that was always going to finalize it. The edge doesn't vanish from the geometry — it silently stops being tracked, and gets rendered as an open ray running straight through territory a third site actually owns. Caught by sampling points along every rendered edge (interior points, not just endpoints) and checking each one is genuinely closer to its own two sites than to any other: 55,780 of 292,560 sampled points (19%) — at least one bad edge in 1,938 of 2,000 random trials (97%) — failed that check before this fix, dropping to 0 of 294,996 after making the split copy both outer edge references, not just create the two inner ones.
Time: O(n log n) with a balanced-tree beach line (supporting
O(log n) arc lookup, split, and removal) and a binary-heap event queue: n
site events plus at most 2n − 5 circle events (one per eventual Voronoi vertex, plus a
bounded number that get scheduled and later invalidated), each doing O(log n) work.
This page's own JavaScript uses a plain linked list for the beach line, walked linearly to
find the arc above a new site, and a sorted array for the event queue — same convention as
Bentley–Ottmann Algorithm's array-backed status
structure — so this specific implementation costs O(n) per lookup and insert rather than
O(log n), O(n²) total; which events get scheduled and which vertices get
found is identical either way, only the per-event bookkeeping cost differs. Space:
O(n) for the beach line, event queue, and finished diagram — the same O(n)
vertex-and-edge bound as the dual Delaunay mesh, reached here without ever building that mesh at
all.
This site's guide, Choosing a Geometry Algorithm, places this entry as the standard real-world route to a Voronoi Diagram when nearest-site regions are the goal and a Delaunay Triangulation isn't needed for anything else.