Voronoi Diagrams Beyond Euclidean Distance

In the Euclidean plane, Voronoi diagrams feel almost inevitable. Pick some sites, partition the plane by nearest site, and you get cells bounded by line segments and rays. But the moment you replace Euclidean distance with something else, the geometry becomes much more interesting.

Under Manhattan distance, bisectors are no longer perpendicular lines. In hyperbolic settings, even intuition about “straightness” becomes local. The combinatorics can remain recognizable while the geometry mutates underneath.

I have recently been interested in the algorithmic question rather than the purely geometric one: what data structures survive when the metric is no longer friendly? The sweet spot seems to be metrics that preserve some convexity, because then local update rules remain tractable.

One practical lesson is to stop hard-coding geometric assumptions too early. If your implementation assumes every bisector is an affine object, you have already limited the mathematics you can explore.

There is also an aesthetic dimension here. Voronoi diagrams are one of the few algorithmic objects that look simultaneously biological and abstract. Change the metric and you change the visual personality of the partition. It feels like changing the musical instrument while keeping the melody.