Voronoi Diagram — Divide & Conquer

A from-scratch implementation of the divide-and-conquer construction of a Voronoi diagram: sort the sites, split, solve each half recursively, merge.

The merge is the interesting part, and the reason this algorithm gets taught. Combining two Voronoi diagrams means constructing the dividing chain between them — the sequence of edges equidistant from the nearest site on either side — and correctly trimming the edges each half already had. Getting the recursion right is straightforward. Getting the merge right is not.

Runs in O(n log n), againstO(n²) for the naive pairwise construction.

This is coursework, not a product. It's on this site because the foundations underneath everything else came from somewhere.