### 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 | Canada |

City | Edmonton |

Period | 8/08/19 → 10/08/19 |

## Fingerprint Dive into the research topics of 'Hardness results on voronoi, laguerre and apollonius diagrams'. Together they form a unique fingerprint.

## Cite this

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*(pp. 99-104)