Suppose there is an unknown closed convex body $K$ of volume vol$(K) = V$ inside the unit cube $[-\frac{1}{2}, \frac{1}{2}]^d$ in $\mathbb{R}^d$. You are permitted to probe with a (one-dimensional) ray $r$, which detects whether $r$ includes some point of $K$, or instead if $r \cap K = \varnothing$. My question is:

Q1. What is the fewest number of such needle probe rays that guarantee hitting $K$, as a function of its volume $V$?

I am especially interested in $\mathbb{R}^3$. For example, for $V \ge \frac{1}{2}$, one ray through the origin parallel to an axis suffices. Here such a ray touches the boundary of a body $K$ with vol$(K)=\frac{1}{2}$:
To be specific:

Q2. How many needle probes suffice for $V \ge \frac{1}{4}$ in $\mathbb{R}^3$?

Four parallel rays in a grid pattern do not suffice, but nine do suffice (I believe):

Q3. In $\mathbb{R}^3$, is it sometimes more efficient to use nonparallel rays?

This feels like a classic problem, but I am not finding literature. Thanks for pointers or ideas!

Update 1 (28May13). Here is Yoav Kallus' example showing that dropping the middle of the $9$ points of the grid permits a triangle with area larger than $\frac{1}{4}$ to avoid detection:

Update 2 (30May13). Q2 and Q3 are now answered by Benjamin Dickman and Douglas Zare: for $V=\frac{1}{4}$, three needles suffice, and more are needed for parallel needles. Q1, in its full generality, is difficult, and so I've added the "open problem" tag.

  • 3
    $\begingroup$ You realize that for small $V$, your question is at least as hard as mathoverflow.net/questions/3307/…, don't you? $\endgroup$ – fedja May 27 '13 at 12:56
  • 1
    $\begingroup$ Do you need the center point in the arrangement of $9$ points to detect $V\ge 1/4$? $\endgroup$ – Douglas Zare May 27 '13 at 13:16
  • 1
    $\begingroup$ By the way, your earlier question is related: mathoverflow.net/questions/106754/… $\endgroup$ – Douglas Zare May 27 '13 at 13:25
  • 2
    $\begingroup$ @Douglas: the center point is needed. Consider the triangle with vertices at (-1/4,1/2), (-1/4,-1/4), and (1/2,-1/4). It has area 9/32 > 1/4. $\endgroup$ – Yoav Kallus May 27 '13 at 14:52
  • 1
    $\begingroup$ @Joseph: Assuming I have correctly understood your Q2, those three needles suffice. (Clearly it is also necessary to have at least three.) This should indicate your Q3 is answered in the affirmative. Surely Q1 is a bit tougher. $\endgroup$ – Benjamin Dickman May 28 '13 at 0:51

If $V \gt 1/2$ then there must be some pair of points $(x,y,z)$ and $(-x,-y,-z)$ contained in the region, and the convex hull of these two points contains the origin. This generalizes to show that $3$ needles connecting the centers of opposite faces (the axes) suffice for $V\gt 1/4$:

Consider the orbits of points under the volume-preserving action of changing signs. Generic points $(x,y,z)$ have orbits of size $8$: $(\pm x, \pm y, \pm z)$. If $V \gt 1/4$ then there must be some orbit so that $3/8$ of the points are contained in the region. Given any $3$ of these points, $2$ must have different signs in at least $2$ coordinates since if the first is $(x,y,z)$ and the second is $(x,y,-z)$, then the third point can't be only a single sign change away from both. If the signs differ in $2$ coordinates, suppose without loss of generality these are $(x,y,z)$ and $(x,-y,-z)$. The convex hull of these points contains the midpoint $(x,0,0)$ which is on the $x$-axis. If the points differ in $3$ signs, then their midpoint is $(0,0,0)$ on all axes.

There is a limit to how much this generalizes, but perhaps the full action of the cubic symmetries will restrict the volumes of regions which avoid the diagonals, too.

  • $\begingroup$ @Douglas: Very clever to consider the volume-preserving action of changing signs! $\endgroup$ – Joseph O'Rourke May 30 '13 at 9:53

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.