Constructing Voronoi Diagrams
Using a Linear Sweep Method
In 1854 a cholera outbreak rampaged in the Soho District of London, England. 616 people died due to lack of proper sanitation. The original theory was that cholera spread through breathing "bad air," but a physician by the name of John Snow disputed this claim. Snow tracked outbreaks and correlated them to water sources in the city; his dot density map clearly displayed a relationship between families who drew their water from certain wells and families who contracted cholera. This early example of a Voronoi diagram was pivotal to both epidemic tracking and understanding the transmission of disease through germs.
Voronoi diagrams are a way to divide a plane into regions based on a distance metric. A standard Voronoi diagram creates a nearest neighbors division based on a set of sites that are inputs. Each region is associated with a site and each point in a region is closer to that site than any other site. Voronoi diagrams are used in variety of biological, engineering, and geometric applications.
Perhaps the easiest way to visualize the construction of a Voronoi diagram is through the concept of growing circles. At each of the given sites, grow circles outward at a continuous rate, marking intersecting edges of the circles as edges in the Voronoi diagram.
Another way to consider the construction of Voronoi diagrams is by taking the intersection of half-planes. A region for a site is determined by the intersection of the perpendicular bisectors for line segments drawn between the given site and all other sites. Using an O(n log n) time half-plane intersection algorithm to compute each region, this method takes O(n2 log n) time to compute a Voronoi diagram for n points.
A faster method of computing Voronoi diagrams is via a divide and conquer strategy. The points are recursively partitioned into two sets - the Voronoi diagrams for the two sets are merged in linear time to give a total time complexity of O(n log n) time.
This site explores an algorithm implemented by Steven Fortune in 1986, which takes O(n log n) time and O(n) space by performing a linear sweep.
Voronoi diagram of Georgy Voronoi ⟶
Though Voronoi diagrams were used by multiple mathematicians, they were formally named in 1908 after Georgy Voronoi, a Russian-Ukranian mathematician. Georgy Voronoi was the first to define Voronoi diagrams for n-dimensions.