Revisiting Random Points: Combinatorial Complexity and Algorithms
share
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 ∈ [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 Õ(n^4/3) time algorithm for the distance selection problem for d=2.
READ FULL TEXT