# Tightly placed sphere caps

Problem. Fix a positive real $$r>0$$ and a positive integer $$n>0$$. Consider an independent, identical sample $$X_1, \ldots X_n$$ drawn from the uniform distribution over the unit $$d$$-sphere $$\mathbb S^d \subset \mathbb R^{d+1}$$. What is the probability that $$\|X_i - X_j\| \le r$$ for every $$(i,j)$$?

I could work out an iterated integral giving an exact formula for $$d=1$$, although the integral itself is quite complicated. Before proceeding further with calculations, I wanted to know if there is a prior literature on this problem. This area of mathematics seems to go by the name of geometric probability (e.g. this 1978 textbook by Solomon).

A similar, well-studied problem is the probability that spherical caps of radii $$r$$ centered at $$X_1, \ldots X_n$$ covers the whole sphere. A spherical cap here refers to sets of the form $$\{ y \in \mathbb{S}^d | \|x-y\| \le r \}$$ for each fixed $$x \in \mathbb S^d$$. For this problem, an exact solution is known for $$d=1$$ (Stevens 1939), and some work on upper and lower bounds of the probability are known for $$d>1$$ (Gilbert 1965). The $$d=1$$ case by Stevens is as follows. The probability that $$n$$ randomly chosen arcs of length $$a$$ from a circle of circumference $$1$$ is equal to: $$\sum_{k = 0}^{\lfloor 1/a \rfloor} (-1)^k \binom nk (1- ka)^{n-1}$$

• I think this paper might be of help: Random Point Sets on the Sphere --- Hole Radii, Covering, and Separation (arxiv.org/abs/1512.07470). Specifically, you're asking about the "separation" part. I think the paper mainly deals with the asymptotics for large n, but might have some info for finite n. Mar 2, 2022 at 23:21
• And arXiv's traceback helpfully reminded me I have previously linked to this paper on MO on a different question. So that question might be relevant too: mathoverflow.net/questions/245027/… Mar 2, 2022 at 23:23
• Thanks for the reference Yoav. I think separation in that paper is the minimum of all pairwise distances, while I am considering the maximum of all pairwise distances. Do you know if this is addressed there or elsewhere? Mar 6, 2022 at 20:32
• Sorry I misread your question the first time. So it sounds like you're asking about the diameter of a random point set? I unfortunately don't recall anything helpful to point you to for that question. A quick search on Google Scholar turned up some papers looking at the diameter of a set of uniformly random point drawn from the ball and from a compact plane set. Maybe those could be helpful. (doc.rero.ch/record/311708/files/10687_2007_Article_38.pdf, doi.org/10.1239/aap/1019160946) Mar 7, 2022 at 3:14
• @YoavKallus thanks a lot! "Diameter" is a better phrasing of the problem I posed. Mar 7, 2022 at 18:32

Not an answer; too long for a comment:

There seem to be extensive results in the paper https://arxiv.org/abs/0712.2816 Coverage processes on spheres and condition numbers for linear programming by Bürgisser et al. I am unsure whether they will help with your problem.

From the abstract:

Let $$p(n,m,\alpha)$$ be the probability that $$n$$ spherical caps of angular radius $$\alpha$$ in $$S^m$$ do not cover the whole sphere $$S^m.$$ We give an exact formula for $$p(n,m,α)$$ in the case $$\alpha \in [π/2,π]$$ and an upper bound for $$p(n,m,\alpha)$$ in the case $$\alpha \in [0,π/2]$$ which tends to $$p(n,m,\pi/2)$$ when $$\alpha \rightarrow \pi/2.$$

In the case $$\alpha \in [0,\pi/2]$$ this yields upper bounds for the expected number of spherical caps of radius $$\alpha$$ that are needed to cover $$S^m.$$

The authors then relate the results to the condition number of a random linear program in $$\mathbb{R}^{m+1}.$$

• Thank you. Do you know if this paper addresses the main question (tightly placing spherical caps) instead of the question of covering a sphere by spherical caps? Mar 2, 2022 at 21:15