Constructing Voronoi Diagrams with Expanding Cells

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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.

[more]

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.

[less]

Contributed by: Erik Mahieu (August 2016)
Open content licensed under CC BY-NC-SA

Details

detailSectionParagraph

Permanent Citation

Erik Mahieu

 Feedback (field required) Email (field required) Name Occupation Organization Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback. Send