Voronoi diagrams can be applied to and used in most science and engineering fields, anything from art and UI to robotics and astrophysics (Lynch, Wikipedia) - almost any circumstance where you have a discrete set of data and care about distance.
2-dimensional Voronoi diagrams are described by a set of points called sites, where each site is contained within its own convex polygon called a cell (Mumm). The secret to the diagram’s applicability lies in these cells: their boundaries are defined so that all points within them are closest to the site also contained within that cell (Dobrin). In other terms, these principles make it easy to determine which site is the closest given any location on the diagram.
Image source: Mumm
Definition of Voronoi Diagrams
How to make a Voronoi Diagram
Image source: Austin
One way to frame the making of Voronoi diagrams is through a series of perpendicular bisectors between the points. We can imagine the base case of having two points and splitting the space with a perpendicular bisector between the points. By the definition of a perpendicular bisector we know that the points along the line are equidistant from the two points it divides and any given point is closest to the point on the side it is on. The image above shows perpendicular bisectors between a point and all the other points in the diagram. It shows that not every bisector influences the cell area. The bisector between the center point and bottom left point does not impact the shape of the diagram.
While this is not a very efficient method for making Voronoi diagrams, it is a great way to understand why the diagram has the borders it does. To learn about a more efficient way of producing a Voronoi diagram, read the article on Fortune's algorithm.
Resources
Austin, David. “Voronoi Diagrams and a Day at the Beach.” American Mathematical Society,
Aug. 2006, www.ams.org/publicoutreach/feature-column/fcarc-voronoi.
Dobrin, Adam. A Review of Properties and Variation of Voronoi Diagrams.
Mumm, Michael. “Voronoi Diagrams.” The Mathematics Enthusiast, vol. 1, no. 2, 2004. Article 4.
Tamassia, Roberto. “Introduction of Voronoi Diagrams.” 22 Mar. 1993.
Commentaires