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]
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]
Free weekly newsletter
Fill out your e-mail address to receive our newsletter!
By entering your email address you agree to receive our newsletter and agree with our privacy policy.
You may unsubscribe at any time.
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]
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.
