0
$\begingroup$

I'm currently doing some mathematical analysis of a system and I have distilled the problem down to a geometry/probability problem. I have a two part problem I would like to solve.

Part 1: Random Points on a Disk

From here, the probability density function of two points (randomly picked, uniformly) on a disk of radius $R$, having a distance between them of at most $s$ is:

$ f(s)=\frac{4s}{\pi R^2}\arccos\frac s{2R}-\frac{2s^2}{\pi R^3}\sqrt{1-\left(\frac s{2R}\right)^2}$

I'd like to adapt this to solve it for $n$ points. The question is this: Given $n$ points randomly distributed across a disk of radius, R, what is the probability that at least two of those points are within $s$ of each other?

My Guess: Take the integral of the above function from $0$ to $s$, and then multiply it by $^nC_2$ . However, this seems too simple. Am I mistaken?

Edit: As saulspatz below stated, this can't be right, because as $n$ increases, $\binom{n}{2}$ goes to $\infty$ , so I'm not sure how to solve this either.

Part 2: Total Expected Area of Overlap

Similar as above, but assume that the $n$ points selected all correspond to centers of circles with radius $r$. What is the expected area of overlap in terns of $n$, $R$ and $r$?

I did a bit of searching and there were a few topics that touched on this, but not really in the scope I was looking for:

Expected area of the intersection of two circles

Expected overlap of n circles of equal area randomly placed inside a circle of larger area

From what I could gather, this is a two part problem.

Part 2a: Area of Intersection of Two Circles

From here I found that the area of intersection of two circles with radii $r_1$ and $r_2$ at a distance $d$ from each other is as follows:

$A_{\textrm{intersection}} = r_1^2 \arccos\left(\frac{d_1}{r_1}\right) - d_1\sqrt{r_1^2 - d_1^2} \nonumber + r_2^2\arccos\left(\frac{d_2}{r_2}\right) - d_2\sqrt{r_2^2 - d_2^2}$

where:

$d_1 = \displaystyle\frac{r_1^2 - r_2^2 + d^2}{2d}$

and

$d_2 = d - d_1 = \displaystyle\frac{r_2^2 - r_1^2 + d^2}{2d}$

Because I'm only interested in circles of the same diameter, $r_1 = r_2 = r$ which can lead to some simplification of the equation above. I'll skip out on these simplifications for now.

Part 2b: Calculating Expected Areas

I'm not sure how to go about doing this here. After I simplify the above, clearly, I'm interested in looking at something $0 < d < 2r$ (if the distance between the two centers were more than $2r$, they would not intersect).

My Guess: I'd have to take some kind of integral of a function which is the product of the probability function $f(s)$ multiplied by the intersect area (setting $d=s$)

But those are only guesses from me. I'm not really sure if any of my guesses are correct (or even in the right direction). Could someone help?

Thank you

$\endgroup$
9
  • 1
    $\begingroup$ Your first guess can't be right, because as $n$ increases, $\binom{n}{2}$ goes to $\infty$ and you will soon get "probabilities" $>1$. $\endgroup$ – saulspatz Dec 2 '19 at 16:45
  • $\begingroup$ Thank you, I've updated the question with your observation. $\endgroup$ – Aommaster Dec 2 '19 at 17:04
  • 1
    $\begingroup$ First, you don't need to integrate the function, because it represents the probability that the distance is $\leq s.$ (It's already the integral of the distribution function.) Second, you need to take inclusion-exclusion into account. If there are $3$ points, let $A_1$ be the event that points $2$ and $3$ are within $s$, $A_2$ the event that points $1$ and $3$ are within $s$ and $A_3$ the event that points $1$ and $2$ are within $s$. Then $$\Pr(A_1\cup A_2\cup A_3)=\Pr(A_1)+\Pr(A_2)+\Pr(A_3)-\Pr(A_1\cap A_2) -\Pr(A_2\cap A_3)-\Pr(A_1\cap A_2)+\Pr(A_1\cap A_2\cap A_3)$$ $\endgroup$ – saulspatz Dec 2 '19 at 17:11
  • 1
    $\begingroup$ Thanks saulspatz. Given this, would it just be better to run a simulation and collect data? I was somewhat hoping for an analytic solution, but doing the exclusions/inclusions like you mentioned would be impractical, as I intend on looking at values around $n=20$ $\endgroup$ – Aommaster Dec 2 '19 at 17:18
  • 2
    $\begingroup$ Continuation. I'm not sure that any of these events are independent; I rather think they're not. Surely, once we know that point $1$ and $2$ are close together, it's more likely that point $3$ is close to both of them than if they are far apart. Even with just two events, I don't think they're independent. A point near the boundary of the disk doesn't have full disk of radius $s$ centered at it and enclosed in the disk. So if points $1$ and $2$ are close together, they're both more likely to be near the center, and that increase the probability that $3$ is close to $1$. $\endgroup$ – saulspatz Dec 2 '19 at 17:22
0
$\begingroup$

You are unlikely to find a closed form expression for the probability of overlap and general $n$. Also, note that that for all $n$ sufficiently large there will be overlaps with probability $1$. Indeed, $n$ disjoint circles of radius $r$ will have a total area of $n\pi r^2$, which exceeds $\pi R^2$ whenever $n>(R/r)^2$.

It is likely that for your application, a sufficiently good approximation of the probabilities in question will be enough, in which case I refer you to the literature in the well-developed field of random spatial models where extremely similar problems are studied.

$\endgroup$
6
  • $\begingroup$ Thank you! Is it possible to develop an analytic solution to the two-circle problem? Two circles randomly selected inside this circle and calculate the union of the areas. If so, could you show me how to do it? $\endgroup$ – Aommaster Dec 3 '19 at 11:23
  • $\begingroup$ For two circles this is doable, yes (which doesn't mean the answer will be pretty). Can you precisely state the problem? Are you looking to find the area of the intersection of two circles of radius $r$ whose centers are picked uniformly and independently at random from a disk of radius $R$? $\endgroup$ – Fimpellizieri Dec 3 '19 at 12:14
  • $\begingroup$ Also, are you interested only in the part of the intersection that lies inside the disk? This probably makes it harder... $\endgroup$ – Fimpellizieri Dec 3 '19 at 12:15
  • $\begingroup$ @Fimpellizieri Either the area of intersection, or preferably, the total area covered the by two circles ($C_1 \cup C_2$). And no, definitely not only the area within the disk. The area outside the disk should also be considered. $\endgroup$ – Aommaster Dec 3 '19 at 12:31
  • $\begingroup$ Finding the intersection and the total area is basically the same problem. $\endgroup$ – Fimpellizieri Dec 3 '19 at 12:33

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.