6

In $\mathbb{R}^3$, what is the minimum length of a curve starting at the origin whose convex hull contains the unit sphere centered at the origin?

I'm looking for an exact answer or bounds.

The answer in $\mathbb{R}^2$ turns out to be $(1 + \sqrt{3} + \frac{7\pi}{6}) \approx 6.397\ldots$. An informal argument can be found here. For a rigorous proof, you can read this published proof (French) or this unpublished proof (English).

The question comes from asking about the best way for a lost hiker to escape a ($d$-dimensional) forest, when he knows the shape/size of the forest and a bound on his distance to the forest boundary. This paper discusses this generalized problem for $d=2$. My question is equivalent to the case of a half-space for $d=3$.

Community
  • 1
dshin
  • 1,525
  • What bounds do you know already? – Jeppe Stig Nielsen Jan 22 '16 at 12:29
  • 1
    @JeppeStigNielsen I've considered a family of curves that visits the vertices of a bounding polyhedron. A trivial bound of $14+\sqrt{3}=15.732\ldots$ can be obtained this way using a cube. Such curves can be altered by having the path first extend to some point outside the polyhedron, which can allow you to skip some vertices. The vertex visits can also be "smoothed". But I haven't computed actual bounds corresponding to these ideas. – dshin Jan 22 '16 at 13:05
  • 1
    What if you made a right "cylinder" whose base face looked like the optimal curve in 2D (with $z=-1$), and repeated that curve as a "roof" at $z=+1$? Maybe it is not better than visiting all eight vertices of a cube? – Jeppe Stig Nielsen Jan 22 '16 at 13:15
  • I think the curve I mention is $\sqrt{\frac73}+(\frac{1}{\sqrt{3}}+\frac{7\pi}{6}+1) \cdot 2 + 2 = \frac{2+\sqrt{7}}{\sqrt{3}}+\frac{7\pi}{3}+4 \approx 14.01$ in length. – Jeppe Stig Nielsen Jan 22 '16 at 13:26
  • The optimal curve in 2D starts at the origin. So applying that here would perhaps unnecessarily constrain your descent to the cylinder base to be along the $z$-axis. Furthermore, the 2D curve ends outside the unit circle. So if you travel straight up to the roof, you'd trace the curve in reverse...but there is no point in going back to the circle center on the roof. So your idea can be optimized. – dshin Jan 22 '16 at 13:29
  • 1
    I have optimized it already. The $\sqrt{\frac73}$ goes from $(0,0,0)$ to $A=(-1,\frac{1}{\sqrt{3}},1)$ on the "roof". then I follow the path like in your English link in height $z=+1$. Then I go vertically down to $z=-1$ (length $2$ vertically down). Finally trace the same kind of curve at $z=-1$, but in "reverse". I never return to the $z$ axis (the line $x=y=0$). – Jeppe Stig Nielsen Jan 22 '16 at 13:32
  • 1
    Ok, that sounds right. We can do better by "unbending" the reverse circuit, so that it consists of just two length-1 segments and a half-circle. This gives $\sqrt{\frac{7}{3}} + \big(\frac{1}{\sqrt{3}} + \frac{7\pi}{6}+1\big) + (2+\pi) + 2 \approx 13.912\ldots$ – dshin Jan 22 '16 at 13:41
  • Let us continue this discussion in chat. – dshin Jan 22 '16 at 13:49
  • 1
    The forward circuit can be improved as well. We go from $(0,0,0)$ to $A'=(-1, \tan(\theta), 1)$ on the roof, with $0<\theta<\frac{\pi}{4}$. On the roof, we travel clockwise from $A'$ in a straight-line to the tangent point $C=(-\cos(2\theta), \sin(2\theta), 1)$, then traverse the unit circle clockwise to the point $D=(0,-1,1)$, then take a straight-line path to $B=(-1,-1,1)$. This path has total length $f(\theta)=\sqrt{(2+\tan^2(\theta))} + \tan(\theta) + \frac{3\pi}{2} + 1 - 2\theta$. Your choice of $A$ corresponds to $\theta=\frac{\pi}{6}$, but that choice of $\theta$ does not minimize $f$. – dshin Jan 29 '16 at 06:18
  • 1
    Rather, the function $f(\theta)$ is minimized at $\theta \approx 0.571\ldots$, where it attains a value of $13.907\ldots$, slightly beating out $f\left(\frac{\pi}{6}\right) \approx 13.912\ldots$. – dshin Jan 29 '16 at 06:21

0 Answers0