A Voronoi diagram is a partition of a plane into regions based on distance to a specific set of points (called seeds or sites). For each seed point, there is a corresponding region consisting of all points that are closer to that seed than to any other seed.
Given a set of points P = \{p_1, p_2, \ldots, p_n\} in the plane, the Voronoi cell for point p_i is:
where d(x, y) is the distance function between points x and y.
There are other ways of measuring distance. We can select these other distance metrics and see how it affects the diagram.
The standard geometric distance
Also called "taxicab distance" or "city block distance", representing movement restricted to grid lines.
Like Manhattan Distance, but takes the maximum of the two absolute differences. Also known as "chessboard distance" since it is the number of moves a king takes to go between two squares on a chessboard.
A generalization of Euclidean and Manhattan distances.
where \theta = \text{atan2}(q_2 - p_2, q_1 - p_1)
A creative distance that adds sinusoidal modulation based on angle, creating flower-like patterns.
where:
Creates asymmetric cells influenced by point velocity and position, with directional bias.
Treats each point as the root of a polynomial and uses Newton's method to find the nearest root from each pixel. Not really a distance metric, but still cool.
This visualization is implemented using WebGL fragment shaders for real-time computation. Each pixel calculates its distance to all seed points using the selected metric. There are more efficient ways to implement voronoi diagrams, but since we have a GPU which can do something quickly for every pixel, we don't need to get fancy. This naive implementation also lends itself to generalizations like choosing different distance functions.