Hardness results on Voronoi, Laguerre and Apollonius diagrams
| Autor: | Kevin Buchin, Castro, P. M. M. D., Devillers, O., Karavelas, M. |
|---|---|
| Přispěvatelé: | Eindhoven University of Technology [Eindhoven] (TU/e), Universidade Federal de Pernambuco [Recife] (UFPE), Geometric Algorithms and Models Beyond the Linear and Euclidean realm (GAMBLE ), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Department of Applied Mathematics [Heraklion], University of Crete [Heraklion] (UOC), Devillers, Olivier, Algorithms, Geometry and Applications, Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | CCCG 2019-Canadian Conference on Computational Geometry CCCG 2019-Canadian Conference on Computational Geometry, Aug 2019, Edmonton, Canada Scopus-Elsevier Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019, 99-104 STARTPAGE=99;ENDPAGE=104;TITLE=Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|