7
$\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$
3
  • $\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$ Jun 1, 2017 at 19:00
  • $\begingroup$ blog.geomblog.org/2013/01/… $\endgroup$
    – Kaveh
    Jun 3, 2017 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$ Jun 12, 2017 at 11:27

2 Answers 2

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$
10
  • $\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$ Jun 1, 2017 at 9:23
  • $\begingroup$ I meant, rather than $R$, of course. $\endgroup$ Jun 1, 2017 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, 2017 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$ Jun 1, 2017 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$ Jun 5, 2017 at 16:38
-9
$\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$
4
  • 2
    $\begingroup$ This will not give uniform distribution on the disk. You need larger $d$ to have larger probability. $\endgroup$ Jun 2, 2017 at 17:14
  • $\begingroup$ Indeed, I knew it but have no solution here. $\endgroup$
    – Wuestenfux
    Jun 2, 2017 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$ Jun 2, 2017 at 23:36
  • $\begingroup$ Easy approximation. $\endgroup$
    – Wuestenfux
    Jun 3, 2017 at 6:28

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.