3
$\begingroup$

Let's say we have N (10,000 for simplicity) small objects (cubes with edge of size 1, or if easier to calculate, spheres with diameter 1), randomly scattered in a large volume, say a cube of dimensions 10,000x10,000x10,000 (or a sphere of diameter 10,000 if easier to calculate).

What is the easiest way to estimate the higher bound of probability that 2 of them will intersect?

I'm interested in simplicity rather than accuracy, e.g. overestimating the higher bound of that probability by 100 or 1000 times is fine. I'm more interested in EASY methodology of estimation.

$\endgroup$
  • 1
    $\begingroup$ This belongs to packing problems domain. The crucial question is about orientation of your small cubes: Are they parallel to the big cube or could they be rotated? $\endgroup$ – Aksakal Feb 15 '18 at 2:51
  • $\begingroup$ The probability that exactly 2 of them will intersect, or the probability that at least 2 of them will intersect? $\endgroup$ – Reinstate Monica May 2 at 23:45
0
$\begingroup$

Let's consider a simpler case - with two objects.

Suppose we have two intervals $I_1$ and $I_2$ of unit length and centers $X_1$ and $X_2$ that we independently and randomly place on a line of length 10. (For ease, I'll pretend that we "drop" an $X$ value and then generate the surrounding interval $I$. I'll also say the larger interval lies on [0,10].)

You can place $X_1$ wherever, except for anywhere in [0,0.5) or (9.5,10] of the interval. (If you place $X_1$ any closer to either edge, the interval will extend beyond the boundary.) Then when you place $X_2$, you need only concern yourself with making sure that a) it does not overlap with $X_1$ and b) it is a "valid placement." (Meaning that it doesn't extend beyond the boundary.)

Place $X_1$ somewhere on the line. Based on the placement of $X_1$, what are the remaining areas where $X_2$ cannot be placed? If $X_1$ is placed somewhere in [1,9], then we can say that $X_2$ can be placed anywhere on [0,10] as long as it doesn't fall in $I_1$. Since $I_1$ is of length 1 and the entire interval is of length 10, the probability that $I_2$ does not overlap with $I_1$ is 90%.

This gets trickier in the case where $X_1$ is placed in (0.5,1) or (9,9.5). This is because, in order for $X_2$ to be a valid placement, it cannot be placed near the boundaries of the larger interval, nor can $I_2$ overlap with $I_1$. It's certainly possible to derive this (and not necessarily difficult!) but depending on how rudimentary this can be and how this generalizes to higher dimensions with different shapes and more objects, you may just want to suppose a conservative case here as calculations for more objects will likely get computationally intensive pretty quickly.

Ultimately, the probability of no overlap is going to be $P(\text{no overlap}) = P(\text{shape 2 doesn't overlap with shape 1})*P(\text{shape 3 doesn't overlap with shape 2 or shape 1})\cdots$. If you disregard any issues with the boundary (i.e. assume that if a shape overlaps with the boundary, it's fine), then you can estimate that the probability that shape $a_i$ does not overlap with shapes $a_1, \ldots, a_{i-1}$ is the ratio of the volume of shape $a_i$ to the remaining volume in the container after filling the container with shapes $a_1, \ldots, a_{i-1}$. Taking the boundary into account makes this more complex. If you assume no boundary issues, then your estimate of no overlap will be conservative, meaning that your estimate of overlap will be anti-conservative.

Per your post, in order to make your estimate of overlapping to be conservative and your estimate of not overlapping to be anti-conservative, you can assume that the center of any object cannot be sufficiently close to the boundary such that part of the object extends beyond the boundary. That is, you are basically making the container smaller because you don't want to risk any object being placed improperly. You can estimate that the probability that shape $a_i$ does not overlap with shapes $a_1, \ldots, a_{i-1}$ is the ratio of the volume of shape $a_i$ to the remaining volume in the smaller container after filling the smaller container with shapes $a_1, \ldots, a_{i-1}$.

Once you estimate the probability of no overlap, you can easily estimate the probability of an overlap by using $P(\text{overlap}) = 1 - P(\text{no overlap}) = 1 - P(a_n \text{does not overlap with} a_{n-1}, \ldots, a_1)•P(a_{n-1} \text{does not overlap with} a_{n-2}, \ldots, a_1) • \cdots$.

Assuming spheres (or that you place each object in a minimal-volume sphere - see comments below) with radii $r$ and the container is a sphere with radius $R$, we have: $\begin{eqnarray*} P(\text{overlap}) &=& 1 - P(\text{no overlap}) \\ &=& 1 - P(a_n \text{does not overlap with} a_{n-1}, \ldots, a_1)•P(a_{n-1} \text{does not overlap with} a_{n-2}, \ldots, a_1) • \cdots \\ &=& 1 - \frac{2\pi r^2}{2\pi R^2-2(n-1)\pi r^2}•\frac{2\pi r^2}{2\pi R^2-2(n-2)\pi r^2}•\cdots \\ &=& 1 - \frac{(2\pi r^2)^n}{\prod_{i=1}^n(2\pi R^2-2i\pi r^2)} \end{eqnarray*}$

If your container isn't a sphere, then replace sphere volume $\pi R^2$ with container volume $V$ and calculate from there.

Hope this helps!

$\endgroup$
  • 1
    $\begingroup$ Since this analysis essentially applies only to spheres, where an exact answer is available, why not report that answer? $\endgroup$ – whuber Jan 6 '16 at 14:29
  • $\begingroup$ I believe this extends to many geometric shapes. For example, if a cube was placed proximate to a boundary such that no cube of equal size could fit in between the first-placed cube and the boundary, the boundary approximation I suggested above should apply, no? $\endgroup$ – Matt Brems Jan 6 '16 at 14:34
  • 2
    $\begingroup$ The problem isn't with the boundary: it's with the fact that the conditional probability that one more shape can fit into the lacuna created by the previous ones depends fundamentally on more than just the positions of the shapes: it also depends on their orientations and on the details of the shapes themselves. To obtain a suitable approximation, you might consider enveloping each shape with (say) a minimal-volume sphere, but then you need a careful analysis of the accuracy of that approximation. $\endgroup$ – whuber Jan 6 '16 at 14:37
  • 1
    $\begingroup$ That's absolutely correct - I just assumed that all objects would be in the same direction. So this would apply to spheres or objects that are all oriented identically. If that's the case, then my analysis applies once each shape is enveloped in a minimal volume sphere. I can edit my post to include an exact answer. $\endgroup$ – Matt Brems Jan 6 '16 at 14:49
  • $\begingroup$ Thank you, Matt. Don't you need to use $2r$ instead of $r$ in your calculations? After all, two spheres of radius $r$ overlap if and only if their centers are within $2r$ of each other. $\endgroup$ – whuber Jan 6 '16 at 17:22

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.