Revisiting Random Points: Combinatorial Complexity and Algorithms

Consider a set P of n points picked uniformly and independently from [0, 1]^d, where d is a constant. Such a point set is well behaved in many aspects and has several structural properties. For example, for a fixed r ∈ [0, 1], we prove that the number of pairs of ^{(P ₂)} at a distance at most r is concentrated within an interval of length O(n log n) around the expected number of such pairs for the torus distance. 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 than previous proofs. In addition, we present simple linear time algorithms to construct the Delaunay triangulation, Euclidean MST, and the convex hull of the points of P. The MST algorithm uses an interesting divide-and-conquer approach. Finally, we present a simple Õ(n⁴/³) time algorithm for the distance selection problem, for d = 2, providing a new natural justification for the mysterious appearance of n⁴/³ in algorithms for this problem.