covering by spherical caps

Question

Consider the unit sphere $\mathbb{S}^d.$ Pick now some $\alpha$ (I am thinking of $\alpha \ll 1,$ but I don't know how germane this is). The question is: how many spherical caps of angular radius $\alpha$ are needed to cover $\mathbb{S}^d$ completely? There is an obvious bound coming from dividing the volume of the sphere by the volume of the cap, but I am assuming this is far from sharp. I assume that the coding theorists among us have considered this sort of question at great length... One can consider either fixed $d$ or asymptotic results for large $d.$

Answer 1

There exist coverings such that each point is covered at most $400 d \log d$ times, and you can improve this bound a little if you look at the covering density, i.e., the average number of times each point is covered. See the "Covering the sphere by equal spherical balls" by Boroczky and Wintsche (available at http://www.renyi.hu/~carlos/spherecover.ps) and Chapter 6 of Boroczky's book "Finite packing and covering". In the other direction, it is widely believed that the covering density grows at least linearly in $d$, but I don't think this has been proved. It's listed as an open problem on page 199 of Boroczky's book, which was presumably up to date when it was published in 2004.

Answer 2

There is a theorem of Rogers that for large $d$, if you want to cover a ball of radius $R$ with balls of radius $r \lt R$ then the volume ratio estimates is almost sharp. (Almost = a polynomial expression in $d$, while the volume ratio is $(R/r)^d$.)

Morally, the same should be true for caps whether you want to cover large caps by smaller caps or the whole sphere by smaller caps. I think this is also a consequence of the result about covering density that Henry mentioned. There is some basic difference between covering and packing in that coverings are much more efficient than packings. But I cannot say I understand the conceptual reason.

When you want to cover by caps which are very close to being half-spheres then again to the best of my memory the problem becomes delicate. You need always $d+2$ by Borsuk-Ulam theorem and the precise smallest radius for which $d+2$ suffices is also not known to the best of my memory.

Answer 3

There's the trivial observation that a maximal packing of balls of radius $\alpha/2$ gives a covering of radius $\alpha$. Thus, an upper bound on the maximal number of disjoint balls of radius $\alpha/2$ gives an upper bound on the number of balls of radius $\alpha$ needed to cover. There is the trivial upper bound on the number of spheres of radius $\alpha/2$ by taking the ratio of volumes, but this can be improved using Boroczky's packing estimate.

Also, check out the second chapter to "Sphere packings, lattices, and groups".

Answer 4

I think that when $d$ is fixed, the first order term when $\alpha\to0$ is given by the case of a suitably renormalized cube of the same dimension $d$. This is what happens when you compute the minimal $L^p$ average distance from a uniform point on a manifold to a set of $N$ points, see Approximation by finitely supported measures.

One important lesson I learned while writing this article is that for this kind of questions, it is worth asking statisticians (see e.g. S. Graf & H. Luschgy Foundations of quantization for probability distributions, Lecture Notes in Mathematics, vol. 1730). Often they work on domains of $\mathbb{R}^d$, but then a cutting method as in the above paper can extend the result to manifolds.

You should get an estimate on the number $N$ of $\alpha$-caps needed to cover $S^d$ of the form $N=\theta(d)\alpha^{-d} + o(\alpha^{-d})$ where $\theta(d)$ is explicit in terms of the volume of $S^d$ and the covering constant of $\mathbb{R}^d$, which is unknown when $d>3$.