Covering compact metric spaces greedily (Q722361)

Let \(X\) be a compact metric space with metric \(d\) defined on it, and write \(B(x,r)\) for the closed ball of radius \(r\) with respect to this metric centered at \(x\) in \(X\). The covering number \(\mathbb N(X,r)\) of \(X\) is defined to be the smallest number of balls of radius \(r\) needed to cover \(X\). The paper under review is concerned with obtaining bounds on \(\mathbb N(X,r)\) for a compact metric space \(X\) carrying a probability measure \(\omega\) on it, i.e., a Borel measure normalized so that \(\omega(X) = 1\). This measure is assumed to be non-degenerate and homogeneous on balls throughout \(X\), hence write \(\omega_r\) for the measure of a ball of radius \(r\). With this setup in mind, the authors prove that \[\frac{1}{\omega_r} \leq \mathbb N(X,r) \leq \frac{1}{\omega_{r-\varepsilon}} \left( \ln \left( \frac{\omega_{r-\varepsilon}}{\omega_{\varepsilon}} + 1 \right) \right).\] The proof of this result is based on a greedy algorithm, iteratively choosing balls to cover the maximal measure of the space yet uncovered. This greedy algorithm has previously been analyzed in the finite setting of the set cover combinatorial optimization problem, in particular by \textit{V. Chvatal} [Math. Oper. Res. 4, 233--235 (1979; Zbl 0443.90066)]. The authors transfer Chvatal's argument to the setting of compact metric spaces to prove their theorem. Then they apply this theorem to three concrete geometric settings, retrieving some of the best known asymptotic results and unifying many results on sphere coverings.