Revisiting Random Points: Combinatorial Complexity and Algorithms

Sariel Har-Peled, 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 e…