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.$
[Math] covering by spherical caps
coding-theorydiscrete geometrymg.metric-geometrysphere packing
Related Solutions
Warning: This is not an answer to the question as posed, just an explanation of my comment at Gil's request. The question itself remains as open as it was!
Let $L$ be the intersection of the unit (radius $1$) ball with the positive orthant $\{x\in\mathbb R^n: x_i\ge 0\ \forall i\}$. Note that the support function of $L$ with respect to the origin is $h_L(\theta)=|\theta_+|$ where $\theta$ is a unit vector and $\theta_+$ is its "positive part" (i.e., all negative coordinates get replaced by $0$). Take small $r>0$ and let $K$ be the convex hull of $L\cup (-rL)$.
Then $h_K(\theta)=\max(|\theta_+|,r|\theta_-|)$, so the width of $K$ in the direction $\theta$ is $h_K(\theta)+h_K(-\theta)|=\max(|\theta_-|,r|\theta_+|)+\max(|\theta_+|,r|\theta_-|)$. Since $|\theta_+|^2+|\theta_-|^2=1$, this is at least $\frac{1+r}{\sqrt{1+r^2}}\ge 1+\frac r2$ for small $r$.
Now let us estimate the volume of $K$ up to a polynomial in $n$ factor. $K$ is the union of the sets $K_{\rho,m}$ consisting of points $x$ with $m$ negative and $n-m$ positive coordinates such that $|x_-|\le\rho$, $|x_+|\le 1-\frac \rho r$. After some usual mumbo-jumbo about $n$ choices of $m$ and a polynomial net in $\rho$, we see that we just need to bound $\max_{m,\rho}|K_{\rho,m}|$.
Now, $|K_{\rho,m}|={n\choose m}\omega_m\omega_{n-m}2^{-n}\rho^m(1-\frac\rho r)^{n-m}$. We want to compare it to the volume of the ball of diameter $1+\frac r2$, which is $2^{-n}\omega_n(1+\frac r2)^n$ ($\omega_k$ is the volume of the $k$-dimensional unit ball). Note that $\frac{\omega_m\omega_{n-m}}{\omega_n}\approx {n\choose m}^{1/2}$ (up to a polynomial factor), so we want to bound $$ {n\choose m}^{3/2}\rho^m(1-\tfrac\rho r)^{n-m}\le\left[ {n\choose m}(\rho^{2/3})^m(1-\tfrac 23\tfrac\rho r)^{n-m} \right]^{3/2} \\ \le (1+\rho^{2/3}-\tfrac 23\tfrac{\rho}{r})^{\frac 32n}\le (1+r^2)^{\frac 32 n}\, $$ so the ratio is essentially $\left[\frac{(1+r^2)^{3/2}}{1+\frac r2}\right]^n$, which is exponentially small in $n$ for fixed small $r>0$.
I re-iterate that it, probably, doesn't say absolutely anything about the original question, but Gil was interested in details, so here they are. BTW, I'll not get surprised if an even simpler construction is possible. I just needed some bounds for self-dual cones and this particular example is merely a byproduct of one failed attempt to prove something decent in another problem...
Here is (I'm fairly sure) an optimal solution, building on the ideas in other answers.
We know that we can generate maximum 30° caps on the sphere, by placing the half-balls at radius sqrt(3)/2. We deduce from http://neilsloane.com/coverings/index.html that we will need 20 half-balls to cover the outer surface, plus a 21st to cover the centre. So, 21 is a lower bound.
To get a 21-ball solution, scale the 20 coordinates of http://neilsloane.com/coverings/dim3/cover.3.20.txt to that radius, and add one at the origin. Note that the balls at sqrt(3)/2 give caps on the central half-ball with the same angle as the outer caps, so the cover works on the inside too.
Here are the coordinates of 21 half-balls to cover the ball: {{+0.060111,-0.479945,-0.718359},{-0.559060,+0.562759,+0.347496},{-0.164091,-0.848680,-0.053063},{-0.509173,-0.375273,-0.591535},{-0.140963,+0.208121,+0.828743},{+0.690970,+0.512659,-0.098697},{+0.377263,-0.700146,+0.342736},{-0.250648,-0.504068,+0.658097},{-0.743210,+0.007958,+0.444494},{+0.550076,+0.074555,-0.664724},{+0.521328,-0.588831,-0.362624},{+0.088527,+0.791576,+0.339956},{-0.158465,+0.221391,-0.822116},{-0.718586,-0.473046,+0.099309},{-0.339530,+0.726217,-0.327609},{+0.439846,-0.237215,+0.707294},{+0.853710,-0.140538,+0.037800},{+0.536789,+0.335659,+0.590924},{+0.243253,+0.709202,-0.433429},{-0.778146,+0.197643,-0.324694},{+0.000000,+0.000000,+0.000000}}
There is some "fat" in the surface covers (using 30° caps when 29.6..° is required), and each non-central sphere bulges convexly out of the cone that it's responsible for, so it's easy to believe that this is indeed a cover. Also I've checked it thoroughly, though I'll be grateful if someone checks it with less makeshift methods. At the positions stated, the radius of the balls can be as low as 0.49812. By moving the original coordinates further inwards, to radius 0.8595, the radius of the balls can be as low as 0.49439.
Ed Wynn, 4 August 2012.[Graphic added by J.O'Rourke:]
Best Answer
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.