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 |