Random point in a d-dimensional ball

I would like to know if there any algorithm to pick a random grid point inside a d-dimensional ball with a given radius R. And if there any algorithm to pick a random arbitrary point inside a d-dimensional ball with a given radius R.

Thanks.

• I was also interested in such an algorithm, and I would be pleased if someone could provide at least something close to pseudo code. Browsed almost whole stack overflow and couldn't find anything getting me closer to the answer. – Brian Atkins Jun 1 '17 at 19:00
• blog.geomblog.org/2013/01/… – Kaveh Jun 3 '17 at 17:13
• The posted answer works well for $R > d^{3/2}$. for smaller $R$, you might want to use the Metropolis algorithm — that should be much more efficient in this case. – Peter Shor Jun 12 '17 at 11:27

For the latter, this discussion is a good starting point. For the former, I guess finding a random point in the ball, rounding it to a grid point, then checking that grid point is in the ball.

• Your algorithm for the first problem will give a nonuniform distribution, as points near the boundary may have lower probability. You may fix it by starting with a random point in a ball with radius $R+1$ rather than $1$. Either way, this will have good probability of success only if $R=\Omega(d)$ or so. – Emil Jeřábek Jun 1 '17 at 9:23
• I meant, rather than $R$, of course. – Emil Jeřábek Jun 1 '17 at 9:44
• True, I suppose you could use $R + (n\delta)^{1/n}$ as your sampling ball radius, i.e., add a grid-cell diagonal width ... – jjg Jun 1 '17 at 9:47
• I see. Since the OP didn’t mention it, I assumed the grid has unit separation, but this doesn’t really matter as everything scales linearly with $\delta$. So, the radius needs to be $R+\frac\delta2\sqrt d$. The expected number of trials is exponential in $\approx d^{3/2}\delta/R$, hence it works well for $R/\delta=\Omega(d^{3/2})$. – Emil Jeřábek Jun 1 '17 at 13:53
• @PengfeiGu The rejection-sampling-with-rounding algorithm works correctly if the sampled body (here, the larger ball) includes all points $x$ whose nearest grid-point $x'$ is in the target ball of radius $R$. Now, $x-x'$ is a vector whose all coordinates are at most $1/2$ in absolute value (assuming unit grid), hence of Euclidean norm at most $\frac12\sqrt d$. Thus, all such $x$ are included in the ball with radius $R+\frac12\sqrt d$ by the triangle inequality. – Emil Jeřábek Jun 5 '17 at 16:38

In view of a circle with center $(a,b)$ and radius $r$, the points $(x,y)$ on the circle fulfill $(x-a)^2 + (y-b)^2 = r^2$. In parametric form, the points are given by $x=a+r\cos\phi$ and $y=b+r\sin\phi$ with angle $\phi$ between 0 and $2\pi$.

Thus finding a random point in the circle is to choose an angle $\phi$ uniformly at random and a number $d$ with $0\leq d\leq r$ uniformly at random.

• This will not give uniform distribution on the disk. You need larger $d$ to have larger probability. – Emil Jeřábek Jun 2 '17 at 17:14
• Indeed, I knew it but have no solution here. – Wuestenfux Jun 2 '17 at 20:28
• Why would you post something you know to be wrong? Not to mention it's an easy special case of the other answer. – Sasho Nikolov Jun 2 '17 at 23:36
• Easy approximation. – Wuestenfux Jun 3 '17 at 6:28