7
$\begingroup$

Suppose that N circles are dropped randomly onto a square in 2-space in such a way that the center of each circle lands somewhere in the square – even if some of the circle extends beyond the boundary of the square. The side of the square is of length S, where S is an integer. Each circle has a real number radius R, where R is a uniformly distributed random value between 0 and some integer M. (Each circle has its own radius of size between 0 and M units). What is the expected number of circles that will not intersect with any other circles?

That was a question from a programming competition 3 weeks ago (http://www.cs.rit.edu/~icpc/questions/2011/Oswego_2011.pdf). My team couldn't solve it, but I really want to know how to. It even inspired me to take a probability course next quarter because I want to know more about that subject.

$\endgroup$
  • 2
    $\begingroup$ Does the radius only take integer values in $\{0,\ldots,M\}$ or is it a continuous random variable taking values in $[0,M]$? $\endgroup$ – cardinal Nov 4 '11 at 23:16
  • $\begingroup$ R is a uniformly distributed random value between 0 and some integer M $\endgroup$ – Pat Needham Nov 5 '11 at 0:31
  • 2
    $\begingroup$ Even that document is not perfectly clear as to what is meant. It is curious that they've specified an integer $M$. However, they also say $R$ is a real number, by which I assume they mean not necessarily an integer. So, it seems what is meant is uniform on $[0,M]$ as opposed to uniform on $\{0,1,\ldots,M\}$. At any rate, they don't want an exact answer, just a Monte Carlo estimate. $\endgroup$ – cardinal Nov 5 '11 at 1:33
8
$\begingroup$

I can see many possible approaches, but let me outline one approach that I think might be effective and might give reasonable accuracy with a reasonable amount of effort. It uses Monte Carlo simulation, independence, and linearity of expectation. I'm going to break it down into bite-sized pieces, by identifying a set of smaller subproblems and explaining how to solve each subproblem, then showing how to combine those solutions to the subproblems to solve the original programming contest problem.

Subproblem 1. Given two circles $C,C'$ in the square, determine whether they intersect.

Solution 1. Let $C$ be centered at the point $(x,y)$ and have radius $r$, and $C'$ be centered at $(x',y')$ with radius $r'$. Note that the two circles overlap if and only if the distance between the two centers is at most $r+r'$, i.e., if and only if $(x-x')^2 + (y-y')^2 \le (r+r')^2$. This condition is easy to test, as a function of $x,y,r,x',y',r'$.

Subproblem 2. Suppose the first circle is given by $C$. Compute the probability $p(C)$ that the second circle will not intersect $C$, as a function of $C$.

Solution 2. We will use Monte Carlo simulation. In particular, perform 10,000 trials, where in each trial, we randomly drop the second circle $C'$ and test whether $C,C'$ intersect (using solution 1 above to test for an intersection). Count the number of trials where they do not intersect and divide by 10,000; that is your estimate of $p(C)$. (It may be possible to solve this subproblem analytically, by solving a three-dimensional integral; however, that does not sound fun. Monte Carlo simulation is easier.)

Subproblem 3. Suppose the first circle is given by $C$. Compute the probability $p'(C)$ that none of the remaining $N-1$ circles will intersect $C$, as a function of $C$.

Solution 3. Note that, by independence, $p'(C) = p(C) \times \cdots \times p(C) = p(C)^{N-1}$. This is easy to compute.

Subproblem 4. Compute the probability $q_1$ that, if you drop $N$ circles randomly, none of the last $N-1$ circles has any intersection with the first circle.

Solution 4. Note that, if we let $C$ be a random variable, we have $q_1 = E[p'(C)]$, where the expectation is taken over $C$. Use Monte Carlo simulation. Perform 10,000 trials, where in each trial you randomly choose a circle $C$, then you compute $p'(C)$ (using solution 3). Average the results over all of the trials. That is your estimate of the probability $q_1$.

Subproblem 5. Compute the probability $q_i$ that, if you drop $N$ circles randomly, the $i$th circle has no intersection with any of the other $N-1$ circles.

Solution 5. By symmetry, $q_i = q_1$, so solution 4 already provides the answer.

The original problem. Compute the expected number of circles that have no intersection with any other circle, if you drop $N$ circles randomly.

Solution. By linearity of expectation, this is $q_1+q_2+\cdots+q_N$. By solution 5, this is $N \times q_1$. Now use solution 4 to compute $q_1$, and you have your answer to the original problem.

$\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.