Selecting two random points inside a sphere which are a fixed distance apart - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T19:02:44Z http://mathoverflow.net/feeds/question/84904 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84904/selecting-two-random-points-inside-a-sphere-which-are-a-fixed-distance-apart Selecting two random points inside a sphere which are a fixed distance apart SeptemberGrass 2012-01-04T21:38:56Z 2012-01-05T02:44:52Z <p>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$. </p> <p>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$? </p> http://mathoverflow.net/questions/84904/selecting-two-random-points-inside-a-sphere-which-are-a-fixed-distance-apart/84914#84914 Answer by Anthony Quas for Selecting two random points inside a sphere which are a fixed distance apart Anthony Quas 2012-01-04T23:03:32Z 2012-01-04T23:03:32Z <p>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 ]</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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. </p> <p>This means that if you take the marginal distribution of either coordinate, it is biased towards being at the centre of the ball.</p> http://mathoverflow.net/questions/84904/selecting-two-random-points-inside-a-sphere-which-are-a-fixed-distance-apart/84922#84922 Answer by Robert Israel for Selecting two random points inside a sphere which are a fixed distance apart Robert Israel 2012-01-04T23:56:06Z 2012-01-04T23:56:06Z <p>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)$ </p>