Voronoi Diagrams

Wikipedia (Voronoi diagram) · CC BY-SA 4.0

Given a set of points (sites), the Voronoi diagram partitions the plane into cells. Each cell contains all points closer to its site than to any other. The boundaries are perpendicular bisectors. Every point in the plane belongs to exactly one cell. Nature uses Voronoi diagrams everywhere: giraffe spots, mud cracks, cell territories.

Nearest-neighbor partition

The Voronoi cell of site p is the set of all points x where d(x, p) ≤ d(x, q) for every other site q. The boundary between two cells is the perpendicular bisector of the segment joining their sites. In 2D, each cell is a convex polygon (possibly unbounded).

Scheme

; Find which site is nearest to a query point
; This is the fundamental Voronoi operation

(define (dist p q)
  (let ((dx (- (car p) (car q)))
        (dy (- (cadr p) (cadr q))))
    (sqrt (+ (* dx dx) (* dy dy)))))

(define (nearest-site query sites)
  (let loop ((best (car sites))
             (best-d (dist query (car sites)))
             (rest (cdr sites)))
    (if (null? rest) best
        (let ((d (dist query (car rest))))
          (if (< d best-d)
              (loop (car rest) d (cdr rest))
              (loop best best-d (cdr rest)))))))

; Five sites
(define sites (list (list 1 1) (list 4 2) (list 2 5)
                    (list 6 4) (list 5 7)))

; Query several points
(for-each
  (lambda (q)
    (display "Nearest to ") (display q) (display ": ")
    (display (nearest-site q sites)) (newline))
  (list (list 0 0) (list 3 3) (list 5 5) (list 6 1)))

Voronoi cells

Each cell is convex. In the Euclidean case, the number of edges per cell is at most 6 on average (by Euler's formula for planar graphs). Cells near the boundary of the point set are unbounded, extending to infinity.

Fortune's algorithm

Computing a Voronoi diagram naively (check every point against every site) is O(n) per query. Fortune's algorithm builds the entire diagram in O(n log n) by sweeping a line across the plane. It maintains a "beach line" of parabolic arcs. As the sweep line moves, arcs grow and shrink. When two arcs pinch off, a Voronoi vertex is found. A parabola is the locus of points equidistant from a point (site) and a line (sweep line).

Scheme

; Fortune's algorithm concept: the beach line
; A parabola is all points equidistant from a focus and a directrix
;
; For a site at (fx, fy) and sweep line at y = d:
; distance to site = distance to directrix
; sqrt((x-fx)^2 + (y-fy)^2) = |y - d|
;
; Solving for y (assuming site is above directrix):
; y = (x-fx)^2 / (2*(fy-d)) + (fy+d)/2

(define (parabola-y fx fy d x)
  (if (= fy d) 999  ; degenerate
      (+ (/ (* (- x fx) (- x fx))
            (* 2 (- fy d)))
         (/ (+ fy d) 2))))

; Site at (3, 5), sweep line at y = 1
(define fx 3) (define fy 5) (define d 1)

(display "Beach line parabola y-values:") (newline)
(for-each
  (lambda (x)
    (display "  x=") (display x)
    (display "  y=") (display (parabola-y fx fy d x)) (newline))
  (list 0 1 2 3 4 5 6))
; At x=3 (directly below site), y is minimal

Applications

Voronoi diagrams answer "which is closest?" for any set of facilities. Post offices, hospitals, cell towers, franchise territories. In computational geometry, they solve the nearest-neighbor problem, the largest empty circle problem, and serve as the foundation for Delaunay triangulations (the dual graph).

Scheme

; Application: nearest facility problem
; Given hospitals and a patient location, find nearest hospital

(define (dist-sq p q)
  (+ (* (- (car p) (car q)) (- (car p) (car q)))
     (* (- (cadr p) (cadr q)) (- (cadr p) (cadr q)))))

(define hospitals
  (list (cons "City General" (list 2 3))
        (cons "St. Mary's"   (list 7 1))
        (cons "County Med"   (list 5 6))
        (cons "Riverside"    (list 1 8))))

(define (nearest-hospital patient)
  (let loop ((best (car hospitals))
             (rest (cdr hospitals)))
    (if (null? rest) best
        (loop (if (< (dist-sq patient (cdr (car rest)))
                     (dist-sq patient (cdr best)))
                  (car rest) best)
              (cdr rest)))))

(for-each
  (lambda (patient)
    (let ((h (nearest-hospital patient)))
      (display "Patient at ") (display patient)
      (display " -> ") (display (car h)) (newline)))
  (list (list 3 2) (list 6 5) (list 1 7) (list 8 2)))

Neighbors

Geometry chapters

△ Chapter 8 — Convex Geometry
△ Chapter 10 — Delaunay Triangulation (the dual)
⚙ Algorithms Ch.8 — the Fortune sweep algorithm for computing Voronoi diagrams
🏷 Aurenhammer 1987 — power diagrams generalize Voronoi to weighted sites

Cross-references

△ Algorithms Ch.8 — geometric algorithms

Foundations (Wikipedia)

Translation notes

Fortune's algorithm is described conceptually here, not implemented. A full implementation requires a priority queue for site and circle events, and a balanced BST for the beach line. The Voronoi SVG is schematic: real Voronoi cells would have edges that are exact perpendicular bisectors. The nearest-site code uses brute-force O(n) lookup per query; a real Voronoi structure enables O(log n) point location.

← Convex Geometry by june.kim Delaunay Triangulation →