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 Proc. $25^{th}$ European Workshop on Computational Geometry EuroCG'09, pages 293-296, Brussels, Belgium, 2009.