covering by spherical caps - MathOverflow

covering by spherical caps

2011-06-12T14:40:25Z

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 by Henry Cohn for covering by spherical caps

2011-06-12T15:39:16Z

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 by Agol for covering by spherical caps

2011-06-12T15:47:29Z

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 by Gil Kalai for covering by spherical caps

2011-06-12T21:07:01Z

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 ration 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+1$ by Borsuk-Ulam theorem and the precise smallest radius for which $d+1$ suffices is also not known to the best of my memory.