Hardness results on Voronoi, Laguerre and Apollonius diagrams - Archive ouverte HAL Access content directly
Conference Papers Year : 2019

Hardness results on Voronoi, Laguerre and Apollonius diagrams

(1) , (2) , (3) , (4)
1
2
3
4

Abstract

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.
Fichier principal
Vignette du fichier
CCCG_2019_paper_40.pdf (342.7 Ko) Télécharger le fichier
Vignette du fichier
vignette.jpg (27.03 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Loading...

Dates and versions

hal-02186693 , version 1 (17-07-2019)

Identifiers

  • HAL Id : hal-02186693 , version 1

Cite

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⟩
95 View
271 Download

Share

Gmail Facebook Twitter LinkedIn More