2026-07-22T01:18:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17902 2024-03-06T11:00:40Z ddc:004 open_access

Abstract Voronoi-Like Graphs: Extending Delaunay’s Theorem and Applications Papadopoulou, Evanthia Voronoi-like graph abstract Voronoi diagram Delaunay’s theorem Voronoi tree linear-time randomized algorithm constraint Delaunay triangulation Any system of bisectors (in the sense of abstract Voronoi diagrams) defines an arrangement of simple curves in the plane. We define Voronoi-like graphs on such an arrangement, which are graphs whose vertices are locally Voronoi. A vertex v is called locally Voronoi, if v and its incident edges appear in the Voronoi diagram of three sites. In a so-called admissible bisector system, where Voronoi regions are connected and cover the plane, we prove that any Voronoi-like graph is indeed an abstract Voronoi diagram. The result can be seen as an abstract dual version of Delaunay’s theorem on (locally) empty circles. Further, we define Voronoi-like cycles in an admissible bisector system, and show that the Voronoi-like graph induced by such a cycle C is a unique tree (or a forest, if C is unbounded). In the special case where C is the boundary of an abstract Voronoi region, the induced Voronoi-like graph can be computed in expected linear time following the technique of [Junginger and Papadopoulou SOCG'18]. Otherwise, within the same time, the algorithm constructs the Voronoi-like graph of a cycle C′ on the same set (or subset) of sites, which may equal C or be enclosed by C. Overall, the technique computes abstract Voronoi (or Voronoi-like) trees and forests in linear expected time, given the order of their leaves along a Voronoi-like cycle. We show a direct application in updating a constraint Delaunay triangulation in linear expected time, after the insertion of a new segment constraint, simplifying upon the result of [Shewchuk and Brown CGTA 2015]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Evanthia Papadopoulou 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.52 urn:nbn:de:0030-drops-179024 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.52 eng https://creativecommons.org/licenses/by/4.0/legalcode