8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brian Atkins Jun 1 '17 at 19:00
  • $\begingroup$ blog.geomblog.org/2013/01/… $\endgroup$ – Kaveh Jun 3 '17 at 17:13
  • $\begingroup$ 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. $\endgroup$ – Peter Shor Jun 12 '17 at 11:27
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jun 1 '17 at 9:23
  • $\begingroup$ I meant, rather than $R$, of course. $\endgroup$ – Emil Jeřábek Jun 1 '17 at 9:44
  • $\begingroup$ True, I suppose you could use $R + (n\delta)^{1/n}$ as your sampling ball radius, i.e., add a grid-cell diagonal width ... $\endgroup$ – jjg Jun 1 '17 at 9:47
  • 4
    $\begingroup$ 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})$. $\endgroup$ – Emil Jeřábek Jun 1 '17 at 13:53
  • 2
    $\begingroup$ @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. $\endgroup$ – Emil Jeřábek Jun 5 '17 at 16:38
-7
$\begingroup$

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.

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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