Nearest neighbourhood operations with generalized Voronoi diagrams: a review

Abstract

An ordinary geographical information system has a collection of nearest neighbourhood operations, such as generating a buffer zone and searching for the nearest facility from a given location, and this collection serves as a useful tool box for spatial analysis. Computationally, these operations are undertaken through the ordinary Voronoi diagram. This paper extends this tool box by generalizing the ordinary Voronoi diagram. The tool box consists of 35 nearest neighbourhood operations based upon twelve generalized Voronoi diagrams: the order-fe Voronoi diagram, the ordered order-fc Voronoi diagram, the farthest-point Voronoi diagram, the kth-nearest-point Voronoi diagram, the weighted Voronoi diagram, the line Voronoi diagram, the area Voronoi diagram, the Manhattan Voronoi diagram, the spherical Voronoi diagram, the Voronoi diagram in a river, the polyhedral Voronoi diagram, and the network Voronoi diagram. Each operation is illustrated with examples and the literature of computational methods.