3
$\begingroup$

Say I have an outer circle of area $\Omega$. If I randomly position n circles of area $\omega$ ($0 \le \omega \le \Omega$) completely inside the outer circle, then what is the expected overlap area of the inner circles?

Assume uniform random positioning. As in, in order to select an inner circle center point, uniformly sample from the points in the outer circle, re-sampling if the point doesn't place the inner circle entirely inside the outer circle.

I've calculated the answer fairly easily through simulation, but I'm looking for an analytic solution $E(overlap)=f(n,\frac{\omega}{\Omega})$.

from simulations I'm pretty sure that $\frac{\partial{f(n,\frac{\omega}{\Omega})}}{\partial{\frac{\omega}{\Omega}}}=g(n)$, and from common sense I know that $f(n,1)=\Omega$ and $f(n,0)=0$, but beyond that I'm stuck.

EDIT: I'm also pretty sure that $f(\inf,\frac{\omega}{\Omega}) = (2\sqrt{\frac{\omega}{\Omega}}-1)^2$

EDIT EDIT: Here are a few examples for $N=3$, $\frac{\omega}{\Omega}=.4$. I randomly placed three circles and highlighted the overlap. ex1 ex2

$\endgroup$
  • $\begingroup$ Are you asking for the area covered by every one of the small circles? $\endgroup$ – Ross Millikan Jul 12 at 20:53
  • $\begingroup$ That is correct $\endgroup$ – Blissasaurus Jul 12 at 20:54
  • $\begingroup$ multiple overlapping considered same as two circle overlapping, I suppose $\endgroup$ – G Cab Jul 12 at 21:04
  • $\begingroup$ @RossMillikanI've attached a few images which I think clarify what I'm looking for. Let me know if anything is still unclear $\endgroup$ – Blissasaurus Jul 16 at 13:24
3
$\begingroup$

Computing the Density for One Disk

Without loss of generalization, let the radius of the larger circle be $1$ and the radius of the smaller circle be $s$.

The probability of a point at a distance $r$ from the center of the circle of radius $1$ being in a circle of radius $s$, whose center is uniformly distributed in a circle of radius $1-s$ concentric with the circle of radius $1$, is the ratio of the area of the intersection of a circle of radius $1-s$ with a circle of radius $s$ whose centers are at a distance $r$ divided by the area of the circle of radius $1-s$.

enter image description here

Using the Law of Cosines and Heron's formula, we get $$ \rho(s,r)=\left\{\begin{array}{} 1&\text{if }r\le2s-1\\[12pt] \frac{s^2}{(1-s)^2}&\text{if }r\le1-2s\\ \frac{s^2\cos^{-1}\left(\frac{r^2+2s-1}{2rs}\right)+(1-s)^2\cos^{-1}\left(\frac{r^2-2s+1}{2r(1-s)}\right)-\frac12\sqrt{\left(1-r^2\right)\left(r^2-(2s-1)^2\right)}}{\pi(1-s)^2}&\text{if }r\gt|1-2s| \end{array}\right. $$


Computing the Density for Multiple Disks

Each of the disks is independent of the others, so the density for the intersection of $n$ disks is $\rho(s,r)^n$. Thus, the expected overlap of all $n$ disks is $$ 2\int_0^1\rho(s,r)^n\,r\,\mathrm{d}r $$ If $0\le r\le2s-1$, then $\rho(s,r)=1$; otherwise, $\rho(s,r)\lt1$. Therefore, $$ \begin{align} \lim_{n\to\infty}2\int_0^1\rho(s,r)^n\,r\,\mathrm{d}r &=2\int_0^{2s-1}r\,\mathrm{d}r\\ &=(2s-1)^2 \end{align} $$ Since $s=\sqrt{\frac\omega\Omega}$, this verifies the formula guessed when $\frac\omega\Omega\ge\frac14$. When $\frac\omega\Omega\lt\frac14$, the limit of the expected values is $0$.


Explanation of the Claim in the Second Paragraph

Symmetry says that the density will be radially symmetric, so we will evaluate at the point $(r,0)$.

Consider $$ \frac1{\pi(1-s)^2}\iint\overbrace{[|t|\lt1-s]}^{t\in B(1-s,0)}\,\overbrace{[|x-t|\lt s]}^{x\in B(s,t)}\,\mathrm{d}t\,\delta(x-(r,0))\,\mathrm{d}x $$ Integrating in $t$ first, we get the average of a disk of radius $s$ whose center has been placed uniformly in the disk of radius $1-s$ centered at the origin. Integrating in $x$, against the delta function, we get evaluation of the resultant average at the point $(r,0)$. This gives the average inclusion probability at $(r,0)$.

The substitution $t\mapsto x-t$ yields $$ \frac1{\pi(1-s)^2}\iint[|x-t|\lt1-s]\,[|t|\lt s]\,\mathrm{d}t\,\delta(x-(r,0))\,\mathrm{d}x $$ and now we can apply Fubini to change the order of integration $$ \frac1{\pi(1-s)^2}\iint[|x-t|\lt1-s]\,\delta(x-(r,0))\,\mathrm{d}x\,[|t|\lt s]\,\mathrm{d}t $$ Integrating in $x$ yields $$ \frac1{\pi(1-s)^2}\int[|(r,0)-t|\lt1-s]\,[|t|\lt s]\,\mathrm{d}t $$ which is the area of the intersection of a disk of radius $s$ and a disk of radius $1-s$ whose centers are separated by a distance $r$ divided by area of a disk of radius $1-s$.

$\endgroup$
  • $\begingroup$ Just finished checking this against simulations, and it looks like everything lines up. Well answered! $\endgroup$ – Blissasaurus Jul 22 at 14:34
  • $\begingroup$ Do you have a source for the probability statement at the top of your answer? I'm trying to generalize to another case and want to check my intuition $\endgroup$ – Blissasaurus Aug 1 at 19:00
  • 1
    $\begingroup$ @Blissasaurus: I have added a section explaining the claim in the second paragraph. $\endgroup$ – robjohn Aug 1 at 21:15
  • $\begingroup$ I appreciate the additional explanation, but do you have a source which inspired your starting point? I'm trying to generalize to different geometries, and would like to see if said hypothetical source mentions anything about them. No worries if not. $\endgroup$ – Blissasaurus Aug 2 at 17:49
  • $\begingroup$ @Blissasaurus: I don't have any source for this. The translational and rotational invariance of $\mathbb{R}^2$ simplifies this problem a bit, but it is still not a simple solution. However, the probability only becomes $1$ when the test point (in this case, $(r,0)$) is guaranteed to be inside the smaller disk. When the probability is less than $1$, the probability vanishes as the number of disks increases. $\endgroup$ – robjohn Aug 2 at 18:38

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.