Hardness results on Voronoi, Laguerre and Apollonius diagrams

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download


https://hal.inria.fr/hal-02186693
Contributor : Olivier Devillers <>
Submitted on : Wednesday, July 17, 2019 - 1:41:04 PM
Last modification on : Wednesday, August 28, 2019 - 2:25:23 PM

Files

CCCG_2019_paper_40.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02186693, version 1

Collections

Citation

Kevin Buchin, Pedro 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⟩

Share

Metrics

Record views

48

Files downloads

420