16
$\begingroup$

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.$

$\endgroup$

4 Answers 4

20
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks! I am not sure what the intuition is for the second statement (that the covering density grows linearly with $d) thought -- I guess I should look at the references... $\endgroup$
    – Igor Rivin
    Jun 13, 2011 at 16:13
  • $\begingroup$ The sample of his book: catdir.loc.gov/catdir/samples/cam051/2003065450.pdf $\endgroup$ Oct 21, 2015 at 13:22
  • 1
    $\begingroup$ Recently we were able to prove almost an $\Omega(d)$ lower bound via algorithmic techniques. However, the bound only applies for "large caps" $\alpha \geq \frac{\pi}{2} - d^{-1/4}$. $\endgroup$ Jan 10, 2020 at 21:03
9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, I had suspected that the small caps version was easier, and you have confirmed it... $\endgroup$
    – Igor Rivin
    Jun 13, 2011 at 16:15
  • $\begingroup$ Theorem 6.5.1 in Boroczky's book linked above shows that $d+2$ caps are optimally placed at the vertices of an inscribed regular simplex, if you want to minimize the covering radius (it's a "folklore theorem"). The book also solves the $d+3$ cap case. $\endgroup$ Dec 11, 2018 at 0:39
8
$\begingroup$

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".

$\endgroup$
3
  • $\begingroup$ Yes, will check out, tnx... $\endgroup$
    – Igor Rivin
    Jun 13, 2011 at 16:14
  • $\begingroup$ I suppose this construction will be exponential in $d$ away from the volume ratio? $\endgroup$ Oct 21, 2015 at 13:15
  • $\begingroup$ The link to springerlink.com is broken. I'm also unable to find any copy saved on the Wayback Machine. $\endgroup$ May 6, 2023 at 10:10
2
$\begingroup$

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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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