Proceedings of the 31st Canadian Conference on Computational Geometry (CCCG 2019), pp. 99–104
Research account
Hardness results on Voronoi, Laguerre and Apollonius diagrams
We show that converting Apollonius and Laguerre diagrams from an already built Delaunay triangulation of a set of n points in 2D requires at least Ω(n log n) computation time. We also show that converting an Apollonius diagram of a set of n weighted points in 2D from a Laguerre diagram and vice-versa requires at least Ω(n log n) computation time as well. Furthermore, we present a very simple randomized incremental construction algorithm that takes expected O(n log n) computation time to build an Apollonius diagram of non-overlapping circles in 2D.
The paper was presented at Canadian Conference on Computational Geometry 19 (CCCG’19), and published in the Proceedings of the 31st Canadian Conference on Computational Geometry, here is the link.