Suppose $m$ points ("sites") are selected on the unit sphere $S^2$. For a given radius $r < \pi$, we can define a disk around any point on the sphere as the set of points at geodesic distance at most $r$ from it. Let $k$ be the maximum number of sites contained in any such disk. Is there a nice lower bound on $k$ in terms of $r$? In other words, what should the function $k(r)$ be so that, no matter where the $m$ sites are placed, we can always find a disk of radius $r$ containing $k(r)$ of them?

I would hope it is simply $m$ times the fraction of the surface area of the sphere covered by a disk. After all, if the average density of sites on the sphere is $m/A$, there must be some disk whose density is at least the average, right? This would be easily proved if you could tile the sphere with disks with no overlap, but you can't, so I'm not sure. If it turns out to depend on the packing density of disks on a sphere, I'll be happy with a reasonable lower bound.

If you replace the unit sphere and the disks with unit ball and smaller balls of radius $r < 1$ in $\mathbb R^3$, and the area ratio with the volume ratio, then the naive guess doesn't work. You can have $m/2$ sites clustered around one point near the surface of the unit ball and the other $m/2$ sites around the antipodal point, so that for $\sqrt[3]{\frac1{2}} < r < 1$, the volume of a ball of radius $r$ is more half that of the unit ball, but you can't get more than $m/2$ sites inside it. Perhaps it still works in some asymptotic sense; I'm curious about anything rigorous that can be said in this case too.

Finally, although I've stated the above question for the 2-sphere and ball in $\mathbb R^3$, I'm also interested in the generalization to higher dimensions.


It turns out that the answer to my first question is really very simple.

Suppose you pick the center of the disk randomly from a uniform distribution on the sphere. Appealing to symmetry, we may infer that the probability that a given site lies within the disk is precisely the fraction of the surface area of the sphere covered by the disk; if the areas of the disk and the sphere are $a$ and $A$ respectively, this probability is $a/A$. By linearity of expectation, the expected number of sites contained in a randomly chosen disk is $ma/A$. Therefore, there must exist some disk which contains at least this many points.

The second question remains open, namely the problem of covering as many as possible of $m$ sites in a unit ball with a smaller ball of radius $r < 1$.

Edit: I hate to edit merely to bump this to the front page, but I wanted to use this solution to answer another question on math.SE, and I'd rather not do that if it has a negative score. For all I know, it might have an error that I haven't noticed. The one person who downvoted did not leave a reason; can anyone else let me know if this solution is incorrect?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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