Structure
Cell boundaries are perpendicular bisectors of nearby sites. Vertices = points equidistant from 3+ sites.
Advertisement
Fortune's sweep-line
O(N log N). Sweep line + beach line (parabolic arcs) + event queue. Standard construction.
Advertisement
Point location
Given query point, find containing Voronoi cell (= nearest site) in O(log N) via trapezoidal decomposition.
Higher dimensions
Cell complexity blows up. Weighted / power Voronoi generalizations.