A Divide-and-Conquer Algorithm for Computing Voronoi Diagrams

摘要

Identifying the closest of a set of locations typically requires computing the distance to each of these locations, given a current position. However, Voronoi Diagrams precompute the geometric areas that each of these locations is closest to in order to ameliorate the cost of computing distances later on. Problematically, the initial computations required to generate a Voronoi Diagram can be computationally expensive. Naive approaches to generating discretized Voronoi Diagrams require every discretized position to be analyzed with the set of locations. This paper introduces a new algorithm to compute discretized Voronoi Diagrams using a divide-and-conquer approach. Rather than calculate every position, our approach calculates the positions at the four corners of a quadrant. If the corners belong to the same region, there is no need to subdivide this quadrant anymore; but if they are different than the original quadrant is subdivided into smaller quadrants. The process is repeated recursively until the entire diagram has been calculated appropriately.