A Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. Those objects are often points (called seeds or sites). A Voronoi diagram partitions the space so that each region (called Voronoi cell) contains all the points closer to one specific seed than to any other seed.

The boundaries between cells have equal distances from their neighboring points.

Generalizations

Voronoi diagrams aren’t limited to just points as seeds, and we can use whatever shapes we want: 1

We can also use a different metrics other than the Euclidean distance for distance. For example, if we use the Manhattan distance, we get a diagram as the following:

Creation

A brute-force way to create the Voronoi diagram is to loop through each pixel, and for each pixel loop though each object to see which one is the closest.

The jump flooding algorithm is a way to generate a fast approximation of the Voronoi diagram.

Applications

Voronoi diagrams is widely applicable in Computer Graphics:

Footnotes

  1. Fast Voronoi Diagrams and Distance Field Textures on the GPU With the Jump Flooding Algorithm « The blog at the bottom of the sea 2 3