2021/12/23 by Gudmundsson, Joachim, Seybold, Martin P., Wong, Sampson
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2112.12350
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 Od(n log(1/ε)/εd-1) and the construction time is within an OD(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 dO(d) improvement in size for the unweighted case and O(d log(n) + d2 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 Od(1/ε(d+3)/2) worst-case size can be computed in near-linear time.