Imagine that, somewhere inside an origin-centered, unit-radius sphere $S$ in $\mathbb{R}^3$, sits a convex body $K$ of volume vol$(K)=\alpha (\frac{4}{3} \pi)$, with $\alpha < 1$ the fraction of the volume of $S$. $K$ is inside $S$ at an unknown but fixed location and orientation. My question is: How many line-probes are needed to detect its presence? A line-probe is a line $L$ whose intersection with $K$ includes a point strictly interior to $K$. One might need many probes to certainly detect the presence of a small-volume $K$.

Let $f(k)$ be the volume fraction $\alpha$ such that (a) there is some body $K$ that is not detected by any fixed set of $k$ probes, and (b) every body with vol$(K) > \alpha$ is detectable by $k$ probes.

I believe $f(1)=\frac{1}{2}$: If $K$ fills a hemisphere, it could "hide" in $S$ from any single probe. But any $K$ with more than half the volume of $S$ necessarily includes the origin, and so a line through the origin would detect it.
   Sphere Probes
It may be that $f(2)=\frac{1}{3}$ by two orthogonal probes that partition $S$ into two spherical caps and the sandwich between, each of $\frac{1}{3}$ the volume of $S$. And perhaps $f(3)=\frac{1}{4}$ via three probes through the origin. But I am uncertain of these values of $f()$. If anyone can hide bodies of larger volumes from these probes, please let me know!

This feels like a question that was likely considered before; if so, a pointer would be appreciated. Of course, the question generalizes to $\mathbb{R}^d$, with various dimensional probes. In $\mathbb{R}^1$ with point-probes, $f(k)=\frac{1}{k+1}$. Edit: Michael Biro suggests in the comments that the $f(2)$ example above could be generalized to establish that also $f(k)=\frac{1}{k+1}$ in $\mathbb{R}^3$.

Update. Here is an illustration of Ilya Bogdanov's argument that my 2nd example does not establish that $f(2)=\frac{1}{3}$:
            Plane cutting sphere

  • $\begingroup$ In $\mathbb{R}^1$, $\: f(k) = \frac2{k+1} \:$, $\:$ not what you wrote. $\;\;\;\;$ $\endgroup$ – user5810 Sep 9 '12 at 21:16
  • $\begingroup$ @Ricky: If you have $k=1$ point-probe, place it at the midpoint of the unit interval/sphere, and then any segment longer than $\frac{1}{2}$ includes the midpoint probe...? My fault for not making clear what I would consider the 1D version. $\endgroup$ – Joseph O'Rourke Sep 9 '12 at 22:32
  • $\begingroup$ Umm..., the unit sphere in $\mathbb{R}^1$ is $\{-1,1\}$, not $\{0,1\}$. $\:$ $\endgroup$ – user5810 Sep 10 '12 at 0:49
  • 1
    $\begingroup$ I think it might be possible to extend the $f(2) = \frac{1}{3}$ example to show that $f(k) \leq \frac{1}{k+1}$. Cut the sphere equitably into two spherical caps and $k-1$ sandwiches, then orient the probes so that when projected along the axis of the sandwiches, they are the center diagonals of a regular $2k$-gon. The ordering of the diagonals seems to matter, and I haven't gone through the details, but I think it should work. $\endgroup$ – Michael Biro Sep 10 '12 at 3:37
  • 2
    $\begingroup$ It seems that your example for $f(2)$ does not provide $\frac13$. Consider a circle passing through two blue endpoints and one red endpoint. The corresponding plane will cut a cap which is not caught by the lines. On the other hand, the blue segment will be a chord but not a diameter, so the radius of the circle will be larger than in your cap, and the volume of the new cap is also larger. $\endgroup$ – Ilya Bogdanov Sep 11 '12 at 8:48

This is visibly closely related to the "maximal empty convex set problem considered in a number of papers, most recently by Dumitrescu et al (see http://arxiv.org/pdf/1112.1124.pdf). That asks for the size of the biggest convex set not containing a fixed point set, and the bound is somewhere between $O(1/n)$ and $O(\log n/n),$ (where $n$ is the number of points) In your question, you are looking at line segments, so this corresponds to the maximal empty convex set problem in the Grassmannian of affine lines, and since the bounds are likely very similar, you get a set of lines of measure somewhere between $O(1/n)$ and $O(\log n/n).$ Going back to $\mathbb{R}^d$ by Crofton, you will be missing a convex set whose surface area is bounded as above, so by the isoperimetric inequality, it's volume is smaller than $O((\log n/n)^{d/(d-1)}).$

This does not answer you question for specific small $n.$

  • 1
    $\begingroup$ Interesting connection to the largest empty convex set, a direction in which I was not looking. Thanks for the tip, Igor! $\endgroup$ – Joseph O'Rourke Sep 10 '12 at 1:08

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.