2026-07-21T20:02:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8763 2024-03-06T10:42:36Z ddc:004 open_access

Deletion in Abstract Voronoi Diagrams in Expected Linear Time Junginger, Kolja Papadopoulou, Evanthia Abstract Voronoi diagram linear-time algorithm update after deletion randomized incremental algorithm Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been an open problem for a long time. Similarly for various concrete Voronoi diagrams of generalized sites, other than points. In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion. We introduce the concept of a Voronoi-like diagram, a relaxed version of a Voronoi construct that has a structure similar to an abstract Voronoi diagram, without however being one. Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible. We formalize the concept and prove that it is robust under an insertion operation, thus, enabling its use in incremental constructions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kolja Junginger and Evanthia Papadopoulou 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.50 urn:nbn:de:0030-drops-87639 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.50 eng https://creativecommons.org/licenses/by/3.0/legalcode