Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Are you looking for a theoretical or a computational answer? –  Koen S Jan 4 '12 at 21:54
    
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? –  SeptemberGrass Jan 4 '12 at 22:02
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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! –  SeptemberGrass Jan 5 '12 at 6:57
add comment

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

share|improve this answer
    
Thanks so much for your answer! –  SeptemberGrass Jan 5 '12 at 6:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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