论文标题
一种有效，实用的算法和用于计算多重加权的Voronoi图的实现
An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams
论文作者
论文摘要
我们提出了一种简单的类似波前的方法，用于计算欧几里得平面中点和直线段的多重加权伏诺曲图。如果可以假定输入位点是随机加权点，则使用所谓的叠加布置[HAR-PELED＆RAICHEL，离散计算。地理。 53：547-568，2015]允许达到$ O（n \ log^4 n）$的预期运行时复杂性，同时仍保持我们方法的简单性。我们基于CGAL实现了加权点作为输入站点的完整算法。对我们实施的实验评估的结果表明，$ o（n \ log^2 n）$是运行时的实际限制。我们的算法还可以扩展到处理添加权重，除了乘法重量外，它还可以产生一个真正简单的$ O（n \ log n）$解决方案，用于求解此问题的一维版本。
We present a simple wavefront-like approach for computing multiplicatively weighted Voronoi diagrams of points and straight-line segments in the Euclidean plane. If the input sites may be assumed to be randomly weighted points then the use of a so-called overlay arrangement [Har-Peled&Raichel, Discrete Comput. Geom. 53:547-568, 2015] allows to achieve an expected runtime complexity of $O(n\log^4 n)$, while still maintaining the simplicity of our approach. We implemented the full algorithm for weighted points as input sites, based on CGAL. The results of an experimental evaluation of our implementation suggest $O(n\log^2 n)$ as a practical bound on the runtime. Our algorithm can be extended to handle also additive weights in addition to multiplicative weights, and it yields a truly simple $O(n\log n)$ solution for solving the one-dimensional version of this problem.
