The Covering Radius of Randomly Distributed Points on a Manifold

We derive fundamental asymptotic results for the expected covering radius | (XN) | for |N| points that are randomly and independently distributed with respect to surface measure on a sphere as well as on a class of smooth manifolds. For the unit sphere | Sᵈ R^d+1|⁠, we obtain the precise asymptotic that | E (XN) N/ N^1/d| has limit | (d+1) ₃+₁/ d^1/d| as |N |⁠, where | d| is the volume of the |d|-dimensional unit ball. This proves a recent conjecture of Brauchart et al. as well as extends a result previously known only for the circle. Likewise, we obtain precise asymptotics for the expected covering radius of |N| points randomly distributed on a |d|-dimensional ball, a |d|-dimensional cube, as well as on a three-dimensional polyhedron (where the points are independently distributed with respect to volume measure). More generally, we deduce upper and lower bounds for the expected covering radius of |N| points that are randomly and independently distributed on a compact metric measure space, provided the measure satisfies certain regularity assumptions.