Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size

Given a set of $n$ sites from $\mathbb{R}^d$, each having some positive weight factor, the Multiplicative Weighted Voronoi Diagram is a subdivision of space that associates each cell to the site whose weighted Euclidean distance is minimal for its points. We give an approximation algorithm that outputs a subdivision such that the weighted distance of a point with respect to the associated site is at most $(1+\varepsilon)$ times the minimum weighted distance, for any fixed parameter $\varepsilon \in (0,1)$. The diagram size is ${\cal O}(n \log(1/\varepsilon)/\varepsilon^{d-1})$ and the construction time is within a factor ${\cal O} (1/\varepsilon^{(d+1)d} +\log(n)/\varepsilon^{d+2} )$ of the output size. As a by-product, we obtain ${\cal O}(\log( n/\varepsilon))$ point-location query time in the subdivision. The key ingredients of the proposed method are the study of convex regions that we call cores, an adaptive refinement algorithm to obtain small output size, and a combination of Semi-Separated Pair Decompositions and conic space partitions to obtain efficient runtime.