In order to understand how we generate Voronoi diagrams, we must first understand what a Voronoi diagram is. If you haven't already, make sure to read the overview and special topic post "What are Voronoi Diagrams?" Let's do a quick overview just in case:
A voronoi diagram is the partitioning of a plane with n points into convex polygons such that each polygon contains exactly one generating point and every point in a given polygon is closer to its generating point than to any other.
To better understand how they are generated, we need to understand that each Voronoi cell is the intersection of n − 1 half-planes induced by the perpendicular bisectors between a point and all other points. In other words, every border is defined by the perpendicular bisector between points.
Image Source: [O’Rourke]
There are several ways to compute Voronoi diagrams:
Divide and conquer
Incremental algorithim
Using delaunay triangulization
Fortune's algorithim
Divide and Conquer
We can partition a plane into a Voronoi diagram using the traditional divide and conquer algorithim. The plane is divided into subsets of equal size recursively and then merged by merging the subsets. Any overlay is dealt with partitioning each face to points closer to site A and points closer to site B. As you might have guessed this method is extremely inefficient with a complexity of O( n log n). [Setter]
Incremental algorithim
A more popular method of computing Voronoi diagrams is using the incremental algorithim. This method inserts sites in random order and incrementally updates the diagram. Each edge of a Voronoi diagram is part of the perpendicular bisector of two points on the plane, since this is the line that partitions the plane between the points. The conceptually simplest method to construct Voronoi diagrams is randomized incremental construction. To add another site to the diagram, locate the cell that contains it and add the perpendicular bisectors between the new site and all sites defining impacted regions. When the sites are inserted in random order, only a small number of regions are likely to be impacted. Like the Divide and Conquer method, the incremental algorithim is also difficult to implement. [Skiena]
Using Delaunay Triangulation
The dual of the Voronoi diagram the Delaunay triangulation is the unique triangulation so that the circumsphere of every triangle contains no sites in its interior. To learn about the duality of Voronoi diagrams and Delaunay triangualtion, read the topic post "Duality of Voronoi diagrams and Delaunay triangualtion." To learn about Deleaunay triangulation, read the topic post "Delaunay triangualtion." In general, this method is more efficent than our first two algorithims. It has a complexity of O(n^4). [Weisstein]
Image Source: [Weisstein]
Fortune's Algorithim
Fortune's Algorithim is the most popular method and was originally published by Steven Fortune in 1986. It is a sweep line algorithim that uses O(n log n) time. At a high level, it takes a set of sites and sweeps the plane from top to bottom to generate intersettions and vertices. This algorithim is more complicated than we could manage to present on this topic post, but you can read in depth about the algoithim in this detailed proof. [Mount]
Image Source: Fortune's Algorithim Wikipedia
Resources
Setter, Ophir. “Contructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer.” acg.cs, Tel Aviv University, June 2009, http://acg.cs.tau.ac.il/projects/in-house-projects/vd-via-dc-of-envelopes/exam_presentation.pdf. Accessed December 2020.
Skiena, Steven. “Voronoi Diagrams.” The Algorithim Design Manual, State University of New York, June 1997, https://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK4/NODE187.HTM. Accessed December 2020.
O’Rourke. “Voronoi Diagrams and Delaunay Triangulation.” cs.jhu.edu, John Hopkins University, 2016, https://www.cs.jhu.edu/~misha/Spring16/11.pdf. Accessed 2020.
Mount, Dave. “Voronoi Diagrams and Fortune's Algorithm.” cs.umd.edu, 2020, https://www.cs.umd.edu/class/spring2020/cmsc754/Lects/lect11-vor.pdf. Accessed 2020.
Weisstein, Eric W. "Delaunay Triangulation." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DelaunayTriangulation.html
Comments