Hardness results on Voronoi, Laguerre and Apollonius diagrams

Kevin Buchin (1) , Pedro M. M. de Castro (2) , Olivier Devillers (3) , Menelaos Karavelas (4)

1 TU/e - Eindhoven University of Technology [Eindhoven]
2 UFPE - Universidade Federal de Pernambuco [Recife]
3 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
4 Department of Applied Mathematics [Heraklion]

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.

Domaines: Géométrie algorithmique [cs.CG]

Kevin Buchin, Pedro M. M. de Castro, Olivier Devillers, Menelaos Karavelas. Hardness results on Voronoi, Laguerre and Apollonius diagrams. CCCG 2019 - Canadian Conference on Computational Geometry, Aug 2019, Edmonton, Canada. ⟨hal-02186693⟩