Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size

Abstract

Given a set of $n$ sites from ${\mathbb{R}}^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+\epsilon )$ times the minimum weighted distance, for any fixed parameter $\epsilon \in (0,1)$. The diagram size is $O_d(n\log (1/\epsilon )/{\epsilon }^{d-1})$ and the construction time is within an $O_D(\log (n)/{\epsilon }^{(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 \emph{optimal size}, up to $\Theta (1{)}^d$-factors. In particular, the obscure $\log (1/\epsilon )$ 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^2\log (1/\epsilon ))$ 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 \emph{bisector coresets}, which may be of independent interest. In particular, we show that coresets with $O_d(1/{\epsilon }^{(d+3)/2})$ worst-case size can be computed in near-linear time.

arXiv commentIn SoCG'24