Fortune's sweep line algorithm — O(n log n) nearest-neighbor partitioning
Sites: 0
About: A Voronoi diagram partitions the plane into cells, each containing all points closer to one site than any other. Fortune's algorithm (1987) computes this in O(n log n) time using a sweep line: as the line moves downward, it maintains a "beachline" of parabolas (one per site, equidistant from that site and the sweep line). Parabola intersections trace Voronoi edges; when three parabolas meet (circle event), a vertex is found. Applications span computational geometry, nearest-neighbor search, mesh generation, geography (Thiessen polygons), and protein structure analysis.