论文标题
重新访问随机点：组合复杂性和算法
Revisiting Random Points: Combinatorial Complexity and Algorithms
论文作者
论文摘要
考虑一个$ n $ p $ $ n $点的$ n $点，从$ [0,1]^d $独立于恒定尺寸$ d $ - 这样的点集在许多方面表现出色。例如，对于[0,1] $中的固定$ r \，我们证明了最多$ r $的$ p $点对点的新浓度结果 - 我们表明此数字仅包含$ o（n \ log n）$数字的间隔。 我们还提出了简单的线性时间算法来构建Delaunay三角剖分，Euclidean MST和$ p $点的凸壳。 MST算法是一种有趣的分裂和争议算法，可能具有独立的关注。我们还提供了一个新的证据，表明$ p $的Delaunay三角剖分的预期复杂性是线性的 - 新证明更简单，更直接，并且可能具有独立的兴趣。最后，我们提出了一个简单的$ \ tilde {o}（n^{4/3}）$ time算法，用于$ d = 2 $的距离选择问题。
Consider a set $P$ of $n$ points picked uniformly and independently from $[0,1]^d$ for a constant dimension $d$ -- such a point set is extremely well behaved in many aspects. For example, for a fixed $r \in [0,1]$, we prove a new concentration result on the number of pairs of points of $P$ at a distance at most $r$ -- we show that this number lies in an interval that contains only $O(n \log n)$ numbers. We also present simple linear time algorithms to construct the Delaunay triangulation, Euclidean MST, and the convex hull of the points of $P$. The MST algorithm is an interesting divide-and-conquer algorithm which might be of independent interest. We also provide a new proof that the expected complexity of the Delaunay triangulation of $P$ is linear -- the new proof is simpler and more direct, and might be of independent interest. Finally, we present a simple $\tilde{O}(n^{4/3})$ time algorithm for the distance selection problem for $d=2$.
