1
$\begingroup$

We have a very big (as in: a unit volume is negligibly small compared to it) volume V, randomly (uniformly and independently) filled with points. The points are the centers of spheres of radius r. The spheres do not overlap (Yes, that means depending on r some points need to be redrawn, and approaching the packing limit the placement will look less and less random). The space is filled to a mean density (spheres' volume to unit V) d.

I'd say a point P, randomly placed inside the volume, has probability d of being inside a sphere.

What about a randomly placed line segment of unit length? What is the probability P(r,d) of it intersecting a sphere at any point?

$\endgroup$
  • $\begingroup$ Infinite volume with uniform probability distribution has some theoretical difficulties. As in, it cannot be done. $\endgroup$ – Arthur Apr 9 at 5:49
  • $\begingroup$ @Arthur ok. How about a very big volume (very big as in a unit volume is negligible?)? --- And can you give me some references about the problem? $\endgroup$ – bukwyrm Apr 9 at 5:52
  • $\begingroup$ Yes, that would work $\endgroup$ – Arthur Apr 9 at 5:55
2
$\begingroup$

Rough answer for the low density case (too long for a comment).

Let $B(r,x)$ denote the sphere of radius $r$ centered at point $x$. Let $C$ be the set of centers of the spheres.

The point $P$ is inside $B(r,c)$ for some $c \in C$ iff $B(r,P)$ contains some $c \in C$. We're saying this prob $= d$.

In the low density case, my guess is that the prob of any region $\Sigma$ (sphere, cube, torus, whatever) containing some $c \in C$ is proportional to the volume of $\Sigma$, as long as this volume $\ll$ the total volume $V$. This is because:

  • Let $X = $ the number of $c \in C$ inside $\Sigma$. By linearity of expectation, $E[X]$ is proportional to the volume of $\Sigma$. (This is true whether density is high or low, and also regardless of the shape of $\Sigma$.)

  • In the low density case and when $\Sigma$ is much smaller than the total volume, the prob that $2$ or more $c \in C$ are inside $\Sigma$ approaches $0$.

  • Therefore, $X$ is actually $\{0,1\}$-valued, i.e. it is an indicator variable, and $E[X] = Prob(X = 1) = Prob(X \ge 1) =$ prob that some $c \in C$ is inside $\Sigma$.

If you believe everything above :) then the answer can be calculated as follows. Consider a line segment $L$ of length $l$, and define $\Sigma$ to be the region of distance $\le r$ from the line segment. This region is a cylinder of radius $r$ around $L$, plus two half-spheres at either end. Its volume is $V_\Sigma = {4\over 3} \pi r^3 + l \pi r^2$.

Meanwhile, in the point $P$ case, we know there is prob $d$ that $B(r,P)$ contains some $c \in C$. Volume of $B(r,P)$ is of course ${4\over 3} \pi r^3$. We're claiming the probabilities are proportional to the volumes, so:

  • $L$ intersects $B(r,c)$ for some $c \in C$ iff $\Sigma$ contains some $c \in C$

  • ${P(\Sigma \text{ contains some } c \in C) \over P(B(r,P) \text { contains some } c \in C)} = {Volume\ \ of\ \ \Sigma \over Volume\ \ of\ \ B(r,P)} = {V_\Sigma \over {4\over 3} \pi r^3}$

  • $P(B(r,P) \text { contains some } c \in C) = d$

  • So: $P(L \text{ intersects } B(r,c) \text{ for some } c \in C) = P(\Sigma \text{ contains some } c \in C) = d \cdot {V_\Sigma \over {4\over 3} \pi r^3}$.


This approach does not work well for the high density case, because in that case $X$ has a non-negligible prob of having values $> 1$. So it is no longer an indicator variable and $E[X]$ overestimates $Prob(X \ge 1)$. As a result, the value calculated above will be an upper-bound only... and often the upper-bound is useless (too loose). For the high density case, this method does not provide a lower bound (beyond the obvious lower-bound of $d$).

E.g. the densest regular sphere packing (in 3-D) has $d \approx 0.74$, and a dense "random" packing has $d \approx 0.64$ according to wikipedia. If the line segment has length $l=\alpha r$, then $V_\Sigma = ({4 \over 3} + \alpha) \pi r^3$ and the ratio of volumes $=({4 \over 3} + \alpha) / {4 \over 3} = {4 + 3\alpha \over 4}$. So the upperbound will be:

$$P(\Sigma \text{ contains some } c \in C) \le d \cdot {4 + 3 \alpha \over 4}$$

For $l=r$ (i.e. $\alpha = 1$), this bound $> 1$ for $d = 0.64$, making it a useless upperbound. I.e. you can conclude the prob of intersect is between $d=0.64$ and $1$, but you already knew that!

However, for really short line segments, this still gives a non-trivial upper-bound, e.g. $l = r/10$ (i.e. $\alpha = 0.1$) and $d = 0.64$ gives an upperbound of $0.688$, so you can conclude, for such a short line segment, the prob of intersect is between $d =0.64$ and $0.688$.

$\endgroup$
  • $\begingroup$ Thank you for your fine answer! the third item after "This is because" - could you have a look at that again? i do not understand it, and suspect it might suffer from wrong parantheses and/ or equalities? $\endgroup$ – bukwyrm Apr 9 at 19:32
  • $\begingroup$ If $X$ is a $\{0,1\}$-valued r.v., then $E[X] = 1 \cdot P(X=1) + 0 \cdot P(X=0) = P(X=1)$. Also since it is $\{0,1\}$-valued, $P(X=1) = P(X\ge 1)$. And of course $X \ge 1$ is exactly the event that some $c \in C$ is inside $\Sigma$. Does this explanation help? Would it help more if I point out that $P(X=1) = P(X \neq 0)$? $\endgroup$ – antkam Apr 9 at 19:48
  • $\begingroup$ The idea of looking at it not as a line in a cloud of spheres, but as a sausage in a cloud of points is very helpful. I still have questions, though. $d = {V_{spheres} \over V_{tot}}$ , right? And shouldn't then $P($any c in $ \Sigma) = d * {V_\Sigma \over V_{spheres}} = {V_\Sigma \over V_{tot}}$. Also, for the densest packing, the spheres do not fill the volume, yet there is no free path anymore, so the probability of the line hitting a sphere is 1. ln that case d is still not 1, so wouldn't your result under estimate in that case? $\endgroup$ – bukwyrm Apr 10 at 5:27
  • $\begingroup$ you seem a little confused between spheres (all of them, with centers $c \in C$) and a single sphere (centered at $P$). I have rewritten that part of the answer. I have also expanded the discussion on the high density case. hopefully my edits help! if you have more questions, feel free to ask. $\endgroup$ – antkam Apr 10 at 13:09

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.