Hardness results on voronoi, laguerre and apollonius diagrams

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

Hardness results on voronoi, laguerre and apollonius diagrams

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

Algorithms

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer 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-2	Engels
Titel	Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019
Pagina's	99-104
Aantal pagina's	6
Status	Gepubliceerd - 10 aug. 2019
Evenement	31st Canadian Conference on Computational Geometry, CCCG 2019 - Edmonton, Canada Duur: 8 aug. 2019 → 10 aug. 2019

Congres

Congres	31st Canadian Conference on Computational Geometry, CCCG 2019
Land/Regio	Canada
Stad	Edmonton
Periode	8/08/19 → 10/08/19

Andere bestanden en links

Link to publication in Scopus

Citeer dit

@inproceedings{0b2f854a5c9d452d9e8c4f304ab26178,

title = "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.",

author = "Kevin Buchin and Castro, {Pedro Mac Hado Manh{\~a}es De} and Olivier Devillers and Menelaos Karavelas",

year = "2019",

month = aug,

day = "10",

language = "English",

pages = "99--104",

booktitle = "Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019",

note = "31st Canadian Conference on Computational Geometry, CCCG 2019 ; Conference date: 08-08-2019 Through 10-08-2019",

}

TY - GEN

T1 - Hardness results on voronoi, laguerre and apollonius diagrams

AU - Buchin, Kevin

AU - Castro, Pedro Mac Hado Manhães De

AU - Devillers, Olivier

AU - Karavelas, Menelaos

PY - 2019/8/10

Y1 - 2019/8/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85073032509&partnerID=8YFLogxK

M3 - Conference contribution

SP - 99

EP - 104

BT - Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019

T2 - 31st Canadian Conference on Computational Geometry, CCCG 2019

Y2 - 8 August 2019 through 10 August 2019

ER -

Hardness results on voronoi, laguerre and apollonius diagrams

Samenvatting

Congres

Andere bestanden en links

Vingerafdruk

Citeer dit