论文标题
方向性和乘法伏罗尼亚图的线性预期复杂性
Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams
论文作者
论文摘要
尽管平面中的标准未加权Voronoi图具有线性最差的复杂性，但其许多天然概括却没有。本文考虑了两个先前研究的概括，即乘法和半伏罗尼亚图。这些图都具有二次最坏情况的复杂性，尽管在这里我们表明它们的预期复杂性对于某些自然随机输入是线性的。具体而言，我们认为预期的复杂性是线性的：（1）当随机采样可见的方向时，半伏罗尼亚图，以及（2）当从恒定尺寸的集合中取样重量时，或者从恒定的情况下采样重量时，则乘法图是乘法图，或者当重量是任意位置时更具挑战性的情况。
While the standard unweighted Voronoi diagram in the plane has linear worst-case complexity, many of its natural generalizations do not. This paper considers two such previously studied generalizations, namely multiplicative and semi Voronoi diagrams. These diagrams both have quadratic worst-case complexity, though here we show that their expected complexity is linear for certain natural randomized inputs. Specifically, we argue that the expected complexity is linear for: (1) semi Voronoi diagrams when the visible direction is randomly sampled, and (2) for multiplicative diagrams when either weights are sampled from a constant-sized set, or the more challenging case when weights are arbitrary but locations are sampled from a square.
