2026-07-21T00:54:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20007 2024-06-06T06:21:16Z ddc:004 open_access

Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size Gudmundsson, Joachim Seybold, Martin P. Wong, Sampson Multiplicatively Weighted Voronoi Diagram Compressed QuadTree Adaptive Refinement Bisector Coresets Semi-Separated Pair Decomposition Lower Bound Given a set of n sites from ℝ^d, each having some positive weight factor, the Multiplicatively Weighted Voronoi Diagram is a subdivision of space that associates each cell to the site whose weighted Euclidean distance is minimal for all points in the cell. We give novel approximation algorithms that output a cube-based subdivision such that the weighted distance of a point with respect to the associated site is at most (1+ε) times the minimum weighted distance, for any fixed parameter ε ∈ (0,1). The diagram size is O_d(n log(1/ε)/ε^{d-1}) and the construction time is within an O_D(log(n)/ε^{(d+5)/2})-factor of the size bound. We also prove a matching lower bound for the size, showing that the proposed method is the first to achieve optimal size, up to Θ(1)^d-factors. In particular, the obscure log(1/ε) factor is unavoidable. As a by-product, we obtain a factor d^{O(d)} improvement in size for the unweighted case and O(d log(n) + d² log(1/ε)) point-location time in the subdivision, improving the known query bound by one d-factor. The key ingredients of our approximation algorithms are the study of convex regions that we call cores, an adaptive refinement algorithm to obtain optimal size, and a novel notion of bisector coresets, which may be of independent interest. In particular, we show that coresets with O_d(1/ε^{(d+3)/2}) worst-case size can be computed in near-linear time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joachim Gudmundsson and Martin P. Seybold and Sampson Wong 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.62 urn:nbn:de:0030-drops-200078 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.62 eng https://creativecommons.org/licenses/by/4.0/legalcode