Detecting a hidden convex body with line probes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T11:16:32Z http://mathoverflow.net/feeds/question/106754 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106754/detecting-a-hidden-convex-body-with-line-probes Detecting a hidden convex body with line probes Joseph O'Rourke 2012-09-09T21:04:25Z 2012-09-11T11:03:37Z <p>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 &lt; 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 <em>line-probe</em> 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$.</p> <p>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.</p> <p>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. <br /> &nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/SphereProbes.jpg" alt="Sphere Probes"> <br /> 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!</p> <p>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}$. <em>Edit</em>: 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$.</p> <p><b>Update</b>. Here is an illustration of Ilya Bogdanov's argument that my 2nd example does <em>not</em> establish that $f(2)=\frac{1}{3}$: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/SpherePlane.jpg" alt="Plane cutting sphere"> <br /></p> http://mathoverflow.net/questions/106754/detecting-a-hidden-convex-body-with-line-probes/106761#106761 Answer by Igor Rivin for Detecting a hidden convex body with line probes Igor Rivin 2012-09-10T00:47:26Z 2012-09-10T00:47:26Z <p>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 <a href="http://arxiv.org/pdf/1112.1124.pdf" rel="nofollow">http://arxiv.org/pdf/1112.1124.pdf</a>). 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 <em>surface area</em> is bounded as above, so by the isoperimetric inequality, it's volume is smaller than $O((\log n/n)^{d/(d-1)}).$</p> <p>This does not answer you question for specific <em>small</em> $n.$</p>