Detecting a hidden convex body with line probes

2012-09-09T21:04:25Z

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.

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}$:

Answer by Igor Rivin for Detecting a hidden convex body with line probes

2012-09-10T00:47:26Z

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.$

Detecting a hidden convex body with line probes - MathOverflow

Detecting a hidden convex body with line probes

Answer by Igor Rivin for Detecting a hidden convex body with line probes