The eighth Geometry entry, and a direct follow-up to Delaunay Triangulation, which named this page in
its own Complexity section and left it unbuilt. Given n sites in the plane, partition the
plane into n regions — one per site, called its cell — where every point
inside a site's cell is closer to that site than to any other. The result is the "nearest facility"
map for the whole plane at once: pick any location, find which cell it falls in, and that cell's site
is its nearest neighbor among all n, with no per-query search needed once the diagram is
built.
The most direct way to build one cell is half-plane intersection. "Closer to site
p than to site q" is exactly one side of the perpendicular bisector of
segment pq — a straight line, since the set of points equidistant from two fixed points
is always a line. "Closer to p than to every other site" is the intersection of
n − 1 such half-planes, one per other site, and the intersection of half-planes is always
a convex polygon. Starting from a bounding rectangle (the plane has to be cut off somewhere to draw
it) and clipping it against each of those n − 1 bisector lines in turn, using the same
Sutherland-Hodgman polygon-clipping idea as clipping any convex shape against a half-plane, leaves
exactly that site's cell. Repeat independently for every site and the union of all n cells
tiles the whole rectangle.
The same 8 points, in the same order, as the Delaunay Triangulation demo — click any point to highlight its own cell, and turn on the Delaunay overlay to see the dual relationship directly: every Voronoi vertex sits at the circumcenter of a Delaunay triangle.
Half-plane intersection is correct almost by definition: a point belongs to site p's
cell exactly when it satisfies "closer to p than q" for every other site
q simultaneously, and intersecting the half-planes one at a time, in any order, computes
precisely that logical AND. The only subtlety is drawing something finite: the true cell of a site on
the point set's convex hull is unbounded, stretching to infinity in some direction, so this page clips
every cell to a fixed rectangle before rendering it. That clip is a viewing choice, not part of the
diagram's actual geometry — see Pitfalls for a case where it visibly matters even for a site that
isn't on the hull.
The duality with Delaunay Triangulation follows from one fact: a Delaunay triangle's circumcenter is equidistant from all three of its vertices by definition, and the Delaunay condition guarantees no other site lies inside that circumcircle — so no other site can be closer to the circumcenter than those three are. That makes the circumcenter simultaneously equidistant-and-nearest to (at least) three sites at once, which is exactly what a Voronoi vertex is: the meeting point of three or more cells. Two sites connected by a Delaunay edge share a Voronoi edge for the same reason turned sideways — every point on the perpendicular bisector between two triangle-adjacent sites is equidistant from just those two and nearer to both than to anything else nearby, because the two triangles on either side of that shared edge are exactly the region where no third site's circumcircle test intervenes. Rotate the whole Delaunay mesh's edges 90° around each edge's own midpoint, in spirit, and what you get is this diagram.
function circumcenter(a, b, c) {
const d = 2 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
const ux = ((a.x**2 + a.y**2) * (b.y - c.y) + (b.x**2 + b.y**2) * (c.y - a.y)
+ (c.x**2 + c.y**2) * (a.y - b.y)) / d;
const uy = ((a.x**2 + a.y**2) * (c.x - b.x) + (b.x**2 + b.y**2) * (a.x - c.x)
+ (c.x**2 + c.y**2) * (b.x - a.x)) / d;
return { x: ux, y: uy };
}
// Clip convex polygon `poly` to the half-plane "closer to p than to q" (Sutherland-Hodgman).
function clipHalfPlane(poly, p, q) {
const qmp = { x: q.x - p.x, y: q.y - p.y };
const c = (q.x ** 2 + q.y ** 2 - p.x ** 2 - p.y ** 2) / 2;
const side = v => v.x * qmp.x + v.y * qmp.y - c; // <= 0 means on p's side (or tied)
const out = [];
for (let i = 0; i < poly.length; i++) {
const cur = poly[i], nxt = poly[(i + 1) % poly.length];
const curIn = side(cur) <= 1e-9, nxtIn = side(nxt) <= 1e-9;
if (curIn) out.push(cur);
if (curIn !== nxtIn) {
const t = side(cur) / (side(cur) - side(nxt));
out.push({ x: cur.x + t * (nxt.x - cur.x), y: cur.y + t * (nxt.y - cur.y) });
}
}
return out;
}
function voronoiCell(site, allSites, w, h) {
let poly = [{ x: 0, y: 0 }, { x: w, y: 0 }, { x: w, y: h }, { x: 0, y: h }];
for (const other of allSites) {
if (other === site) continue;
poly = clipHalfPlane(poly, site, other);
}
return poly;
}"Interior to the convex hull" doesn't mean the true cell fits inside whatever window you draw it in — and the failure is common, not a rare edge case. A site strictly inside the point set's convex hull always has a finite Voronoi cell in theory (its incident Delaunay triangles form a closed fan, and the cell is exactly the polygon of their circumcenters), so it's tempting to assume the canvas-clipped diagram shows that cell exactly whenever the site isn't on the hull. Point 6 in the demo above (at canvas coordinates 180, 200) is interior to the hull, yet its cell as drawn has 5 vertices, not the 4 its incident Delaunay triangles predict — one of those triangles, (80, 300)–(220, 80)–(180, 200), is thin enough (all three points nearly collinear) that its circumcenter lands at (−70, 50), comfortably outside the 560×380 canvas, confirmed by checking that point's distance to all three triangle vertices is identical (≈291.5) to rule out a circumcenter-formula bug rather than a real far-away point. The diagram substitutes two rectangle-boundary crossings for that one true vertex — still a correct clip of the true (unbounded-in-this-window) shape, but not the same polygon the dual graph predicts. This isn't a cherry-picked worst case: across 5,000 random 8-point layouts in the same 560×380 window (13,041 total interior-site instances, deterministic seeded PRNG for reproducibility), 68.7% of interior sites had at least one incident circumcenter fall outside the canvas. Any fixed drawing window is a bet that every relevant circumcenter lands inside it, and thin or near-collinear triangles — common with only 8 points scattered over a wide rectangle — lose that bet more often than not.
Time: O(n³) as shown above: building each of the n
cells clips a polygon against n − 1 half-planes, and each clip costs time proportional to
the polygon's current size, which is O(n) in the worst case — O(n²) per
cell, O(n³) total. This page builds each cell independently by design, to make the
dual-graph check above a genuine cross-check rather than reusing structure the Delaunay build already
produced. The cheaper real route reuses that structure directly: build the Delaunay triangulation once
— O(n²) naive, as on this site's own Delaunay Triangulation page, or O(n log
n) expected with the randomized incremental point-location structure named there — then read the
dual graph off it in O(n): one circumcenter per triangle, one Voronoi edge per Delaunay
edge. Fortune's algorithm builds the
diagram directly in O(n log n) without going through Delaunay Triangulation at all,
sweeping a line down the plane and maintaining a "beach line" of parabolic arcs — the standard
real-world approach, built as this site's next Geometry entry. Space:
O(n) cells, each with O(n)
vertices in the worst case before clipping — O(n²) total, though in practice (no
degenerate co-circular clusters) the whole diagram has only O(n) vertices and edges
combined, the same bound as the dual Delaunay mesh.
This site's guide, Choosing a Geometry
Algorithm, places this entry alongside two cheaper real routes to the same nearest-site
partition: reading the dual straight off an already-built
Delaunay Triangulation in O(n),
or building it directly with Fortune's Algorithm
in O(n log n) — this page builds each cell independently instead, deliberately, to
make the duality check a genuine cross-check rather than reused work.