covering by spherical caps - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T10:29:59Z http://mathoverflow.net/feeds/question/67582 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/67582/covering-by-spherical-caps covering by spherical caps Igor Rivin 2011-06-12T14:40:25Z 2011-06-12T21:55:18Z <p>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.$ </p> http://mathoverflow.net/questions/67582/covering-by-spherical-caps/67587#67587 Answer by Henry Cohn for covering by spherical caps Henry Cohn 2011-06-12T15:39:16Z 2011-06-12T15:39:16Z <p>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 <a href="http://www.renyi.hu/~carlos/spherecover.ps" rel="nofollow">http://www.renyi.hu/~carlos/spherecover.ps</a>) 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.</p> http://mathoverflow.net/questions/67582/covering-by-spherical-caps/67588#67588 Answer by Agol for covering by spherical caps Agol 2011-06-12T15:47:29Z 2011-06-12T17:33:21Z <p>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 <a href="http://www.springerlink.com/index/r357731637812255.pdf" rel="nofollow">Boroczky's packing estimate</a>. </p> <p>Also, check out the second chapter to "<a href="http://books.google.com/books?id=upYwZ6cQumoC&amp;lpg=PP1&amp;pg=PR64#v=onepage&amp;q&amp;f=false" rel="nofollow">Sphere packings, lattices, and groups</a>". </p> http://mathoverflow.net/questions/67582/covering-by-spherical-caps/67602#67602 Answer by Gil Kalai for covering by spherical caps Gil Kalai 2011-06-12T21:07:01Z 2011-06-12T21:55:18Z <p>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$.) </p> <p>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. </p> <p>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. </p>