Revisiting Random Points: Combinatorial Complexity and Algorithms
Sariel Har-Peled, Elfarouk Harb · Society for Industrial and Applied Mathematics eBooks · 2024
Consider a set P of n points picked uniformly and independently from [0, l]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 (p2) 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.