I have radius $r < \frac{1}{2}$ congruent balls with centers randomly distributed uniformly within a region, say, within a unit-radius sphere $S$. I shoot a ray/path through $S$, hoping to intersect many balls. The cost of my probe is the length of the ray within $S$; the payoff is the number of balls intersected. My question is:

Q0. What is the optimal shape of the ray, as a function of $r$?

For example, above shows $100$ balls of radius $r=\frac{1}{10}$. On the left I shoot a (green) straight-line ray of length $2$, and pierce $3$ (red) balls, for a hit/length ratio of $1.5$. On the right I shoot a spiral ray of length $3.57$ through the same distribution of balls (but displayed rotated), and pierce $4$ balls, for a hit/length of $1.1$.

Intuition might suggest that the shape of the ray probe is irrelevant. But this cannot be correct, for a jittery path with deviations much smaller than $r$ is inefficient in that such oscillations increase the path length without increasing the likelihood of intersecting more balls.

It may be possible to answer the following 'No' without entirely resolving Q0:

Q1. Is the optimal shape in fact a straight-line probe, independent of $r$?

An answer 'Yes' to Q1 answers Q0 as well.

  • 5
    $\begingroup$ The expected number of balls the ray intersects should be the volume of an $r$-neighborhood of the path. $\endgroup$ – HenrikRüping Feb 15 '15 at 3:18
  • 1
    $\begingroup$ Great question, but you may want to rethink the title... $\endgroup$ – Jonathan Beardsley Feb 15 '15 at 4:38
  • 4
    $\begingroup$ I think you want to rule out a very short chord somehow. $\endgroup$ – Douglas Zare Feb 15 '15 at 6:17
  • 1
    $\begingroup$ As Douglas Zare suggests, a tangent line has infinite expected hit/length ratio. $\endgroup$ – S. Carnahan Feb 15 '15 at 10:19
  • $\begingroup$ @DouglasZare & SCarnahan: Good point re boundary effects. $\endgroup$ – Joseph O'Rourke Feb 15 '15 at 12:11

From HenrikRüping's comment, we want to consider the volume of an $r$-neighborhood of the topological arc $\gamma$.

Hotelling proved that the volume of an embedded tubular neighborhood of an arc only depends on the length. The $D^2 \times \gamma$ can fail to be embedded due to local or nonlocal self-intersections, both of which decrease the volume. As long as it does not come back near itself or have curvature greater than $1/r$, the $r$-neighborhood of the arc has volume $\pi r^2 |\gamma| + \frac{4}{3} \pi r^3$.

There is a generalization due to Weyl for neighborhoods of higher dimensional submanifolds. The surprise is that the volume depends on intrinsic properties of the submanifold and not on the embedding otherwise.

H. Hotelling. "Tubes and spheres in n-spaces, and a class of statistical problems." Amer. J. Math., vol. 61 (1939), pp. 440-460.

H. Weyl. "On the volume of tubes." Amer. J. Math., vol. 61 (1939), pp 461-472.


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.