Voronoi Diagrams and GIS

Mark Altaweel

Updated:

Voronoi diagrams have become popularized since the 19thcentury in understanding spatial patterns and display of given phenomena, where they were used to map cholera outbreaks in London (related: John Snow’s Cholera Map using GIS Data).

The idea of these diagrams is they are convex polygons that are generated by a single point and the generating points are closer to their polygon points than other polygon points. These polygons represent a division of a plane in areas based on a defined distance to a set of points. Each partition is called a cell.

Different forms of tessellation define different types of polygon layouts. Voronoi diagrams are also called Thiessen polygons, where they often use Delaunay criterion to calculate.[1]

Challenges of Using GIS to Create Voronoi Diagrams

While there are both raster and vector based approaches to define voronoi diagrams, vector based approaches tend to be more complex for area maintenance. Thus, often approaches apply a raster-based approach to define tessellations.[2]

A black and white diagram showing voronoi cells with red triangles marking the set of points.
Voronoi cells form the boundaries for the area on a map that is closest to each point in a set. Diagram: Caitlin Dempsey.

Voronoi diagrams, because they are based on how other polygons will be tessellated, can take a long time to computer. Thus, parallel algorithms and distributed computing methods have been applied for large area and complex tessellations.[3]

Challenges that have been addressed in voronoi research within GIS and spatial methods include creating complex voronoi shapes for the Earth’s surface, where the complex geometry of the surface creates complexity for runtime.

Distance transform methods can be used to calculate distances between land surfaces, enabling the tessellation to be possible. However, such an approach often leads to some level of inaccuracy, as distances have to be estimated and calculation could take too long to generate given tessellations. Thus, grid resolution could be utilized to determine the level of needed accuracy, where the tessellation tolerates some level of defined error.[4]

Shaded elevation map with Voronoi cells overlayed with white boundaries for the California and Nevada region.
A map showing voronoi polygons for elevation points of interest. Each Voronoi cell represents the area on the map that is closest to each elevation point within that cell. Map: Caitlin Dempsey using Natural Earth data.

Applications of Voronoi Tessellations

As for applications, voronoi tessellations have been used in a variety of analyses such as understand the spread of disease in epidemiology research and creating services areas.

In recent work, one application has been to determine socioeconomic relationships for schooling in a province in China. In this case, a so-called crystal-growth tessellation is used to represent a weighted method where a continuous socioeconomic data are divided into discrete origin points.[5]

Other approaches to voronoi research have included using 3D GIS to better represent how cameras are placed for security reasons. Optimizing where cameras need to be placed to fully capture a 3D space can be calculated through a voronoi calculation and then tested through what the placement of the cameras captured, which measures how well the algorithm defines the boundary of the voronoi space for observation.[6]

Voronoi diagrams have also been utilized in visualizing other continuous spatial data, including in 3D, where other methods have traditionally been used, such as spatial autocorrelation and kernel density methods.

In one example, these voronois help indicate where crime concentrates and where policing efforts could most payoff by patrolling and focusing on specific neighborhoods in urban contexts.[7]In other cases, voronoi help to differentiate space of human activity.

For instance, using rail stations as points, the density of activity within these stations produces a space with given weights across a space that then are used to define areas where commuting traffic is present relative to other surrounding regions.[8]

For typical use, voronoi diagrams can be created by many GIS packages today. Popular packages, including ArcGIS, GRASS, and QGIS have plugins that the user community or primary developers have created.

Their wide area of application indicates that this long-lived class of methods will continue to see development to improve their implementation and calculation, particularly for complex spaces and geometries.

References

[1]For more on methods for voronoi calculations, see:  Worboys, M. & Duckham, M. (2004) GIS: a computing perspective. 2nd ed. Boca Raton, Fla, CRC Press, pg. 190.

[2]For more on raster and vector tessellation, see:  Chen, J. (1999) A raster-based method for computing Voronoi diagrams of spatial objects using dynamic distance transformation. International Journal of Geographical Information Science. [Online] 13 (3), 209–225. Available from: doi:10.1080/136588199241328.

[3]For more on parallel algorithm approaches, see:  Wang, J., Cui, C., Rui, Y., Cheng, L., et al. (2014) A parallel algorithm for constructing Voronoi diagrams based on point-set adaptive grouping: Parallel algorithm for voronoi diagrams. Concurrency and Computation: Practice and Experience. [Online] 26 (2), 434–446. Available from: doi:10.1002/cpe.3005.

[4]For more on tessellations using voroni methods on Earth’s surface, see:Hu, H., Liu, X. & Hu, P. (2014) Voronoi diagram generation on the ellipsoidal earth. Computers & Geosciences. [Online] 73, 81–87. Available from: doi:10.1016/j.cageo.2014.08.011.

[5]For more on the crystal-growth tessellation, see:  Wang, J., Kwan, M.-P. & Ma, L. (2014) Delimiting service area using adaptive crystal-growth Voronoi diagrams based on weighted planes: A case study in Haizhu District of Guangzhou in China. Applied Geography. [Online] 50, 108–119. Available from: doi:10.1016/j.apgeog.2014.03.001.

[6]For more on 3D GIS of voronoi visualization of cameras, see: Yaagoubi, R., Yarmani, M., Kamel, A. & Khemiri, W. (2015) HybVOR: A Voronoi-Based 3D GIS Approach for Camera Surveillance Network Placement. ISPRS International Journal of Geo-Information. [Online] 4 (2), 754–782. Available from: doi:10.3390/ijgi4020754.

[7]For more on the use of voronoi diagrams in crime observation and prevention, see:  Melo, S.N. de, Frank, R. & Brantingham, P. (2017) Voronoi Diagrams and Spatial Analysis of Crime. The Professional Geographer. [Online] 69 (4), 579–590. Available from: doi:10.1080/00330124.2017.1288578.

[8]For more on voronoi calculations for rail activity, see: Mota, D.R., Takano, M. & Taco, P.W.G. (2014) A Method Using GIS Integrated Voronoi Diagrams for Commuter Rail Station Identification: A Case Study from Brasilia (Brazil). Procedia – Social and Behavioral Sciences. [Online] 162, 477–486. Available from: doi:10.1016/j.sbspro.2014.12.229.

Related

Photo of author
About the author
Mark Altaweel
Mark Altaweel is a Reader in Near Eastern Archaeology at the Institute of Archaeology, University College London, having held previous appointments and joint appointments at the University of Chicago, University of Alaska, and Argonne National Laboratory. Mark has an undergraduate degree in Anthropology and Masters and PhD degrees from the University of Chicago’s Department of Near Eastern Languages and Civilizations.

Free weekly newsletter

Fill out your e-mail address to receive our newsletter!
Email: