Random point on hyperspherical cap

Question

I have the cap of an n-sphere which is given by a n-dim vector for the center and by another vector which lies on the edge of the cap, both in Cartesian coordinates. The cap should be "circular" or rather an (n-1)-sphere, so these two vectors should be enough to fully describe it.

Now I want to generate a random point which is uniformly distributed on that cap.

I know that a random vector on the n-sphere can be created by drawing n numbers from a normal distribution and normalizing the resulting vector. (see http://mathworld.wolfram.com/SpherePointPicking.html (16))

And there are answers for the 3 dimensional case (see Generate a random direction within a cone), but I am not sure how to extrapolate that to higher dimensions.

Rejection sampling is not possible, since I am dealing with n around 1000, so I would have to reject LOTS of samples, especially if my cap is small.

Answer 1

A point distribution is uniform if the density is everywhere proportional to the "area". If you take spherical coordinates in $n$ dimension, $(r,\phi_1,\ldots,\phi_{n-1})$, wikipedia says that the spherical volume element is $$\mathrm d^nV = r^{n-1}\sin^{n-2}(\phi_1)\sin^{n-3}(\phi_2)\cdots\sin(\phi_{n-2})\mathrm dr\mathrm d\phi_1\mathrm d\phi_2\cdots\mathrm d\phi_{n-1}$$ from which we deduce that the spherical surface element is $$\mathrm d^{n-1}S = \mathrm d^nV/\mathrm dr = r^{n-1}\prod_{i=1}^{n-1}\sin^{n-1-i}(\phi_i)\mathrm d\phi_i$$

EDIT: The above can be rewritten as $$\mathrm d^{n-1}S = \left(r^{n-2}\prod_{i=2}^{n-1}\sin^{n-1-i}(\phi_i)\mathrm d\phi_i\right) \times\left(r\sin^{n-2}(\phi_1)\mathrm d\phi_1\right) = r\sin^{n-2}(\phi_1)\mathrm d\phi_1\mathrm d^{n-2}S$$ thus as Chris Jones justly remarked in the comments, it's sufficient to sample $\phi_1$ from a distribution proportional to $\sin^{n-2}(x)$, and sample a point from a lower dimensional sphere uniformly, to reach the desired result.

From there, we thus have to pick the spherical coordinate $\phi_i$ from a pseudo-distribution whose pdf is $\sin^{n-1-i}$. Pseudo-distribution because a proper pdf must integrate to 1. To get the actual pdf, we have to normalize the function, so it'd be $$\mathrm{pdf}_i(x) = \frac{\sin^{n-1-i}(x)}{\int_{\phi_{i,\min}}^{\phi_{i,\max}}\sin^{n-1-i}(t)\mathrm dt}$$ For a spherical cap that admits $Ox_1$ as its axis, $\phi_1$ should range from $0$ to the angular opening of the cap, $\arccos\left(\frac{\vec c.\vec e}{r^2}\right)$, $\phi_{n-1}$ ranges from $0$ to $2\pi$, and all the remaining $\phi_i$ range from $0$ to $\pi$.

If you sample every $\phi_i$ with the pdf's above, you will end up with a point in the spherical cap, and the distribution will be uniform.

---

As of currently, I don't see a simple way to sample these random variables like for the $2$-sphere. The "trick" of uniformly sampling a random variable $z$ on the range $[r\cos\theta,r]$ only works because it is basically an application of inverse transform sampling, where everything is easy to compute.

I don't know what language or software you are using, but in all likelihood, you should be able to find tools that can sample an arbitrary random variable if you provide it with the pdf. I have no clue how fast/efficient these methods are.

Answer 2

Joriki's answer in the other thread to which you linked is still applicable. Your first vector defines the "$z$" direction. $\theta$ is the angle between your two vectors. $\phi$ represents all the other coordinates.

If your two vectors are $\vec c$, representing the center vector and $\vec e$ being the point on the edge, and if $r$ is their common norm (the radius of your $n$-sphere). Then you can

• pick $t$ uniformly from $\left[\dfrac {\vec c \cdot \vec e}{r^2}, 1\right]$
• pick $\hat v$ uniformly from a $n-1$ sphere of radius $1$ in $\vec c^\perp$, the space of all vectors perpendicular to $\vec c$, as indicated in the mathworld link.

The point on your cap will be $$(r\sqrt{1-t^2})\hat v + t\vec c$$

Note that this will be simpler if you pick your random point for $\vec c = (r, 0,0,...)$, whose perpendicular space is easy to represent, then rotate it (by any convenient rotation) to the actual direction of $\vec c$.