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, Geometry and Applications

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019
Pages	99-104
Number of pages	6
Publication status	Published - 10 Aug 2019
Event	31st Canadian Conference on Computational Geometry, CCCG 2019 - Edmonton, Canada Duration: 8 Aug 2019 → 10 Aug 2019

Conference

Conference	31st Canadian Conference on Computational Geometry, CCCG 2019
Country/Territory	Canada
City	Edmonton
Period	8/08/19 → 10/08/19

Cite this

@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

Abstract

Conference

Other files and links

Fingerprint

Cite this