4
$\begingroup$

Without appealing to a guess-and-check approach, how might I select a pair of random points inside of a sphere of radius $R$ s.t. the points always a distance $d \leq R$ apart? Can the selected points be 'random' in the sense that a large number of such pairs can be split into two equal-sized populations that independently appear uniformly distributed within the sphere's volume? If it simplifies matters, and I'm not sure it would, I would also be interested in the case of a cube of edge-length $R$.

So that I can better understand the distribution of point pairs: Imagine I select a pair of points meeting the above separation distance criterion. If I randomly select another such pair, what is the probability that the distance between the first points in either pair is $\leq \delta_1$, and the distance between the second points in either pair is $\leq \delta_2$ for some $\delta_1,\delta_2 \leq R$?

$\endgroup$
2
  • $\begingroup$ Are you looking for a theoretical or a computational answer? $\endgroup$
    – Koen S
    Jan 4, 2012 at 21:54
  • $\begingroup$ I'm not sure I understand? I'm looking for a description of a method, and to understand how the pairs of points will be distributed in the volume of the sphere? $\endgroup$ Jan 4, 2012 at 22:02

2 Answers 2

5
$\begingroup$

From an algorithmic point of view, a very simple and computationally effective way to produce points is exactly the guess and check that you say you don't want. [ You don't say, but I'm assuming you're working in 3 dimensions? As the dimensionality increases, so the methods that I'm talking about become progressively worse ]

Let $X$ be a randomly chosen point in the ball of radius $R$; let $Z$ be a randomly chosen point in the ball of radius 1. Then set $Y=X+dZ/|Z|$. If $Y$ lies in the sphere of radius $R$, then keep the pair $(X,Y)$; otherwise generate a new pair.

This is efficient because it's simple to generate points in a ball and the expected number of attempts you have to make to get a valid pair is small (if you take a spherical shell of radius $d$ centred at a point on the boundary of a ball of radius $R$, a lower bound for the probability of success is the proportion of the shell lying inside the ball. I haven't done the calculation, but this must be large, even for $d=R$.) Since the success probability is high, you don't have to repeat too often to get a valid pair.

Next notice that each pair of valid points has the same chance of being selected so that you are truly picking from the distribution you want.

To answer your question about uniform distribution, you can see from the construction that the first coordinate (and hence the second coordinate also since the distribution is symmetric) is not uniformly distributed in the sphere. For example if $d$ is a lot smaller than $R$, then if you pick $X$ near the boundary of the sphere, the probability of the pair being rejected is about 50%, whereas if you pick $X$ far from the boundary then the probability of rejection is 0.

This means that if you take the marginal distribution of either coordinate, it is biased towards being at the centre of the ball.

$\endgroup$
1
  • $\begingroup$ This is pretty much the same as my current approach, save for that I'm picking the second point on the surface of a sphere about the first in a different manner. However, it's very useful that this this jumps out to other folks as a reasonable strategy! $\endgroup$ Jan 5, 2012 at 6:57
2
$\begingroup$

I'm assuming this is in 3 dimensions. Note that if you first select $X$ in the ball of radius $R$ and take $Y = X + d Z$ where $\|Z\| = 1$, then $\|Y\|^2 = \|X\|^2 + d^2 + 2 d \|X\| \cos \theta$ where $\theta$ is the angle between $X$ and $Z$. Noting that the area of a spherical cap of opening angle $\theta$ is proportional to $1 - \cos \theta$, we see that the probability of $Y$ being in the ball is $\min\left(1, \frac{1}{2} + \frac{R^2 - \|X\|^2 - d^2}{4 d \|X\|}\right)$. So you could select $X$ using a distribution proportional to this factor times the uniform density in the ball, then select $Z$ uniformly in the spherical cap $\cos \theta \le \min\left(1, \frac{R^2 - \|X\|^2 - d^2}{2d\|X\|}\right)$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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