Voronoi diagram: partitions the plane into cells, each containing points closest to one site.
Fortune's algorithm (1987) runs in O(n log n) using a sweep line + beach line (union of parabolas). Events: site events (new parabola) and circle events (Voronoi vertex).
The Delaunay triangulation (dual graph) has the property that no site lies inside any circumcircle — maximizes minimum angle.