Divide-and-Conquer for Voronoi Diagrams Revisited

O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, E. Pilgerstorfer, and M. Rabl

Abstract:

We propose a simple and practical divide-and-conquer algorithm for constructing planar Voronoi diagrams. The novel aspect of the algorithm is its emphasis on the top-down phase, which makes it applicable to sites of general shape.

Reference: O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, E. Pilgerstorfer, and M. Rabl. Divide-and-conquer for voronoi diagrams revisited. In $25^{th}$ Ann. ACM Symp. Computational Geometry, pages 189-197, Aarhus, Denmark, 2009.