Constructing Voronoi Diagrams with Expanding Cells
Constructing Voronoi Diagrams with Expanding Cells
This Demonstration shows how a Voronoi diagram can be constructed from a set of expanding cells centered at a given number of sites. Depending on the distance function, the cell can be a disk or polygon.
A Voronoi diagram has polygons formed around points called sites. Any point inside a polygon is closer to its site than to any other site. Small cells with centers at the sites expand uniformly without overlapping. Once the area is completely covered, a Voronoi diagram is formed.
To realize this in Mathematica for the Euclidean distance function, 3D cones are used (disks or cylinders would overlap). A top view of a set of cones centered at the sites and with equal but expanding base radii produces a Voronoi diagram when the complete base area is covered.
For the Manhattan or chessboard distance functions, the cones are replaced with pyramids over a rhombus or square.