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.
|Title of host publication||Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019|
|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||31st Canadian Conference on Computational Geometry, CCCG 2019|
|Period||8/08/19 → 10/08/19|