Applications | Voronoi & The World

Vast Applications of Voronoi Diagrams

Maps

What the United States would look like if state borders were defined by distance to the state capital.

Starbucks and COVID-19 Tests

Suppose we have a map with marked points for certain locations (like Starbucks or COVID-19 testing locations in a city). If one wanted to know the best location to add another Starbucks or COVID-19 testing site, they could make a Voronoi diagram and then use the largest empty circle problem. The largest empty circle problem is for finding the largest circle that can be drawn on the diagram that contains no sites (in this case, Starbucks or COVID-19 tests). This would mean that the people located at or near the center of this circle need to travel the furthest distance to get to their closest site. Therefore, often the best place for a new location is at the center of this largest empty circle. To find this circle, first, we must define the space where the center of the circle can be in, as the smallest convex polygon that contains all of the sites (Aurenhammer). The center of the largest empty circle must be at an intersection of Voronoi edges (a Voronoi vertex) or at the intersection of an edge and the convex polygon boundary (Aurenhammer). If we define a Voronoi diagram as V(p), for each vertex (and edge/polygon intersection) in the diagram, qiV(p) there is a unique empty circle with center qi (Dobrin). The largest empty circle can then be found by making circles centered at each qiand making them bigger until the edge contacts two or three points (Aurenhammer). Finally, the radius of each circle can be compared to determine the largest.

This map shows the Voronoi diagram of Starbucks locations in part of the Boston area with some potential largest empty circles. Based on this diagram, if Starbucks was looking to add another location in this area, the best place would be the center of the circle in the bottom right.

This map shows the Voronoi diagram of COVID-19 testing locations in part of the Boston area with five candidates for the largest empty circle. While three of the five circles have centers outside of the area being considered, they can be eliminated to show that the center of the south-most circle is the best place for a new testing location when seeking to minimize travel distance for everyone.

Other Applications

Voronoi diagrams can be applied to most science and engineering fields (Lynch). They can be used in most situations with a discrete set of data where distance can be analyzed (Mumm). There are too many applications to describe them all in detail here, but we have included a list below with sources that describe many ways Voronoi diagrams have been used.