2019/11/27 by Hinrichs, Aicke, Krieg, David, Kunsch, Robert J. +1 · 1 citation
#52B55 #62D05 (Primary) #65Y20 #68Q25 (Secondary) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1911.12074
The dispersion of a point set in [0,1]d is the volume of the largest axis parallel box inside the unit cube that does not intersect with the point set. We study the expected dispersion with respect to a random set of n points determined by an i.i.d. sequence of uniformly distributed random variables. Depending on the number of points n and the dimension d we provide an upper and lower bound of the expected dispersion. In particular, we show that the minimal number of points required to achieve an expected dispersion less than ε∈(0,1) depends linearly on the dimension d.