I have a collection of $n$ unit-radius disks in $\mathbb{R}^3$, whose centers are random within a sphere of radius $R>1$, and which are each oriented randomly. I'd like to find a line $L$ that pierces as many disks as possible: $L$ "spears" the "hoops," the circle boundaries of the disks.

This question arose thinking about accidental line-of-sight alignment of galaxies.

          $n=100$ disks centers within $R=10$ of origin (red). $L$ pierces $5$ disks.

Q1. What is growth rate of the expected largest number of piercings by a line $L$, growth with respect to $n$ as $R$ remains fixed?

I expect it grows more slowly than linearly with $n$. Update. @YCor shows in a comment that, in fact, it grows at least linearly.

I'd like to find a max-piercing $L$ without using Plücker coordinates and intersecting regions on the Grassmannian manifold, which I expect to be a non-trivial implementation challenge.

Q2. Is there an "easy" way to find a max-piercing $L$, even if computationally inefficient?

  • 8
    $\begingroup$ (I assume $R$ is fixed). Fix a line $L_0$ passing through the center. The probability that a given circle is pierced by $L_0$ is $p=p(R)>0$ (which can be computed, but I won't). So for $n$ independently chosen circles, the expectation of the number of circles pierced by $L_0$ is $pn$. Hence the sup over all lines (as considered in Q1) is $\ge pn$. $\endgroup$ – YCor Dec 7 '17 at 14:57
  • 1
    $\begingroup$ As a special case: given a plane with various ellipses of major axis 1, what is a good algorithm for determining the point inside a maximal number of ellipses? $\endgroup$ – Matt F. Dec 11 '17 at 21:16
  • 1
    $\begingroup$ Is it true that four ellipses have nonempty intersection iff all four triples among them have nonempty intersection? If so we could reduce the planar problem to a combinatorial one. $\endgroup$ – Matt F. Dec 12 '17 at 3:23
  • 2
    $\begingroup$ @MattF That's Helly's theorem I think. $\endgroup$ – J.J. Green Dec 12 '17 at 8:04
  • 1
    $\begingroup$ Is it true that 5 ellipses in R^3 are speared by a single line iff all 4-tuples among them are speared by a single line? If so we could reduce the actual problem to a combinatorial one. $\endgroup$ – Matt F. Dec 13 '17 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.