Hardness results on voronoi, laguerre and apollonius diagrams

Kevin Buchin, Pedro Mac Hado Manhães De Castro, Olivier Devillers, Menelaos Karavelas

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.

Original languageEnglish
Title of host publicationProceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019
Pages99-104
Number of pages6
Publication statusPublished - 10 Aug 2019
Event31st Canadian Conference on Computational Geometry, CCCG 2019 - Edmonton, Canada
Duration: 8 Aug 201910 Aug 2019

Conference

Conference31st Canadian Conference on Computational Geometry, CCCG 2019
Country/TerritoryCanada
CityEdmonton
Period8/08/1910/08/19

Fingerprint

Dive into the research topics of 'Hardness results on voronoi, laguerre and apollonius diagrams'. Together they form a unique fingerprint.

Cite this