My question is whether there exist algorithms to determine a minimal (or close to minimal) cover of a Riemannian manifold (or some subset thereof) with balls of a fixed radius r>0.
1 Answer
As it is a version of set-cover, the problem is NP-hard. The following is a special case:
(1) Chepoi, Victor, and Bertrand Estellon. "Packing and covering $\delta$-hyperbolic spaces by balls." In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 59-73. Springer, Berlin, Heidelberg, 2007. Springer link.
"In this note, we consider the problem of covering and packing by balls and union of balls of hyperbolic metric spaces and graphs."
(2) Singhof, Wilhelm. "Minimal coverings of manifolds with balls." Manuscripta Mathematica 29, no. 2-4 (1979): 385-415. Springer link.
My understanding is that Singhof links the covering number $B(M)$ of a manifold $M$ to the Lusternik-Schnirelmann category $\operatorname{cat} M$ of a manifold.
You might find later literature, especially for (2), that relies on or expands upon these results.