Hardness results on voronoi, laguerre and apollonius diagrams

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

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.

Originele taal-2Engels
TitelProceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019
Pagina's99-104
Aantal pagina's6
StatusGepubliceerd - 10 aug 2019
Evenement31st Canadian Conference on Computational Geometry, CCCG 2019 - Edmonton, Canada
Duur: 8 aug 201910 aug 2019

Congres

Congres31st Canadian Conference on Computational Geometry, CCCG 2019
LandCanada
StadEdmonton
Periode8/08/1910/08/19

Vingerafdruk Duik in de onderzoeksthema's van 'Hardness results on voronoi, laguerre and apollonius diagrams'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Buchin, K., Castro, P. M. H. M. D., Devillers, O., & Karavelas, M. (2019). Hardness results on voronoi, laguerre and apollonius diagrams. In Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019 (blz. 99-104)