5
$\begingroup$

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.

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks a lot for your answer. I will accept it, although I am not sure how to implement it yet. Maybe there is some nice approximation for the inverse of the cdf. If not, I will try to find some other sampling methods. I am not really limited to any language, but a solution for Python or C would be convenient. $\endgroup$
    – C. Yduqoli
    May 31, 2018 at 7:08
  • 1
    $\begingroup$ @C.Yduqoli For a python solution, you could check this link. Although it's marked as duplicate, I like the top answer more, since it makes use of this scipy class. This way you won't even have to worry about the implementation if you just provide the pdf. As a comment observes, if this turns out to be too slow for your needs, you will probably have to implement your own sampling process. $\endgroup$
    – N.Bach
    May 31, 2018 at 10:57
  • 2
    $\begingroup$ You can actually just use one angle $\phi_1$ drawn from a distribution proportional to $\sin^{n-2}(x)$. Once you have $\phi_1$, the remaining coordinates are a random point from a sphere in $(n-1)$, which can be obtained by normalizing a random Gaussian. To sample from the $\sin^{n-2}(x)$ distribution, as long as $x << \frac{\pi}{2} - \frac{1}{\sqrt{n}}$ then approximating $\sin(x) \approx x$ is ok, and you can exactly solve the inverse transform sampling equation to get that $T*\sqrt[n-1]{u}$ will sample it, where $u \sim [0,1]$ uniformly and $T$ is the angle of the spherical cap. $\endgroup$ Apr 29, 2019 at 22:22
  • $\begingroup$ Whoops, the approximation $\sin^{n-2}(x) \approx x^{n-2}$ is only good when $x = O(\frac{1}{\sqrt{n}})$ i.e. the caps are really really tiny. $\endgroup$ Apr 29, 2019 at 23:22
  • $\begingroup$ @ChrisJones Now that you've pointed it out, it seems so obvious! I'll throw in an edit when I have time (and if I don't forget). $\endgroup$
    – N.Bach
    Apr 30, 2019 at 13:54
0
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Are you sure about this one? I was under the impression that Joriki's answer was only valid because of that property of $2$-spheres, that any slices of equal height have the same surface area. Since I don't know the actual proof, I'd have to check it in more details, but I'm pretty sure this doesn't hold in higher dimension. So this method should(?) fail in OP's case. $\endgroup$
    – N.Bach
    May 28, 2018 at 19:12
  • $\begingroup$ To generate a random point for the space perpendicular to $\vec c = (1, 0,0,...)$, I simply have to pick a random point on the (n-1)-sphere and add 0 as the first component, right? $\endgroup$
    – C. Yduqoli
    May 29, 2018 at 4:35
  • $\begingroup$ A sphere generated using this method looks correct, a circle seems not to be completely uniform. See imgur.com/a/0svWHkF. $\endgroup$
    – C. Yduqoli
    May 29, 2018 at 7:16
  • $\begingroup$ @C.Yduqoli In the circle case, the most straightforward uniform sampling is to have $\theta$ uniformly distributed over $[0,2\pi)$. With Paul's suggestion, the distribution is uniform over $z=\cos\theta$, meaning that you have more points where cosine varies slowly (near $z=\pm 1$), and fewer points where it varies quickly (near $z=0$). $\endgroup$
    – N.Bach
    May 29, 2018 at 12:41
  • 1
    $\begingroup$ @C.Yduqoli My comment was mostly to confirm your experimental result through theory, it wasn't a suggestion for a better method. After looking into things for a bit, I'm certain this doesn't work in higher dimensions. $\endgroup$
    – N.Bach
    May 30, 2018 at 14:26

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.