2026-10-21T09:12:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12911 2024-03-06T09:51:03Z ddc:004 open_access

Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams Fan, Chenglin Raichel, Benjamin Voronoi Diagrams Expected Complexity Computational Geometry While the standard unweighted Voronoi diagram in the plane has linear worst-case complexity, many of its natural generalizations do not. This paper considers two such previously studied generalizations, namely multiplicative and semi Voronoi diagrams. These diagrams both have quadratic worst-case complexity, though here we show that their expected complexity is linear for certain natural randomized inputs. Specifically, we argue that the expected complexity is linear for: (1) semi Voronoi diagrams when the visible direction is randomly sampled, and (2) for multiplicative diagrams when either weights are sampled from a constant-sized set, or the more challenging case when weights are arbitrary but locations are sampled from a square. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chenglin Fan and Benjamin Raichel 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.45 urn:nbn:de:0030-drops-129111 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.45 eng https://creativecommons.org/licenses/by/3.0/legalcode