Exploration of a Polygon Decomposition Technique Based on the Ordinary Voronoi Diagram

Document Type


Publication Date



Voronoi diagrams, spatial analysis, representation

Digital Object Identifier (DOI)



Voronoi diagrams have been integral to the efforts aimed at reducing the difficulty of representing and modeling spatial phenomena. This article extends a polygon decomposition procedure based on ordinary Voronoi diagrams (OVDs) that can produce substitute representations for contiguous polygon objects in spatial analytic situations. It is based on a relatively unexplored conceptual linkage between polygon objects in a vector environment and their ordinary Voronoi-based counterparts. It facilitates the ability to represent typical polygon data with OVDs by exploiting the regularity inherent to the spatial configuration of the polygons in data structures. A discussion is provided for complexity issues and other theoretical concerns associated with using the decomposition procedure. A series of examples to explore the accuracy of the Voronoi-based representations is presented, including one using them in a geographic information system (GIS)-based spatial analysis of the bus transit coverage problem. Results suggest that the Voronoi approach may successfully reproduce polygon data in certain analytical situations and reduce the complexity of spatial operations when using large datasets. A time complexity analysis with sample data is also performed, which demonstrates computational savings attributable to the approach. Given this experience with the technique, several possibilities for future research are laid out.

Was this content written or created while at USF?


Citation / Publisher Attribution

Annals of GIS, v. 16, issue 4, p. 223-236