Home Bookmarks Papers Blog

# Revisiting Random Points: Combinatorial Complexity and Algorithms

Sariel Har-Peled, and Elfarouk Harb.
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$.
PDF. : arXiv.