0
$\begingroup$

Consider two disks: $S$ with radius $R_S$ and position $(x_S,y_S)$, and $M$ with radius $R_M$ and position $(x_M,y_M)$. Let's denote the difference between these two sets as

$$V=S\setminus M.$$

Now the problem is: given two uniformly distributed random numbers $a,b\in[0,1]$, assuming $V\ne\emptyset$, compose from them a uniformly distributed point $p=(x,y)\in V$.

The most obvious solution would be to generate a point $p_0=f(a,b)\in S$ (where $f$ is simple to construct) and, if $p_0\in M$, then discard it, otherwise return $p_0$. But for large overlaps between $S$ and $M$ (e.g. solar eclipse just before totality, with $S$ being the Sun and $M$ the Moon) this strategy will be grossly inefficient due to high rejection rate.

A better approach is to find the thinnest annulus $A$ with outer radius being $R_S$ and inner radius just small enough to fit $V$ into $A$. If we sample only inside the annulus (which is a simple modification of sampling in a full disk), we'll drastically reduce the rejection rate.

But this is still not the best. I suppose there should be a simple way to generate random points in $V$ without rejection at all. But I can't seem to find a way. How can this be done?

$\endgroup$
0
$\begingroup$

With rejection, a simple improvement might be the following: assume WLOG that $y_S=y_M$ , $x_S-R_S < x_M-R_M$, so that one has the zone depicted in the figure. Let $h$ be the height of the smallest containing rectangle, let $t= (x_M-R_M) - (x_S-R_S)>0$.

Then, first map the square to a rectangle $a' = a t$ , $b'=b h$ . In this way, we get uniform points inside the green rectangle. Then shift $a'$ to the right so that it gets inside the red circle (arrows). If the resulting point is outside the $V$, discard and retry.

enter image description here

It would be possible to do something similar without rejection, but it looks quite cumbersome. Now we would shift and scale $a'$, so that it always get into $V$. But then, $b'$ should have been remapped so that its probability density is not uniform but proportional to the lentgh of the corresponding horizontal segment inside $V$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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