2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.