A Hybrid Divide-and-Conquer Algorithm for Computing Voronoi Diagrams

Voronoi diagrams are used in numerous fields from Biology and Medicine to Geography and Cartography. The wide variety of uses of Voronoi diagrams across this disparate fields requires computationally efficient algorithms. While existing Divide-and-Conquer methods prevent unnecessary computations for sub-problems that are all within the same region, the computational cost of continuing to sub-divide problems in degenerate cases is higher. In this paper, we propose a hybrid of the Divide-and-Conquer method and the naive approach for discretized Voronoi diagrams. We present the original and updated algorithms and a variety of comparisons on computational costs.