Can you explain this answer to Bellman's Lost in a Forest in 3D?

176 Views Asked by At

The problem is as follows: Ignoring forces, there is a spaceship a known distance away from a planet; though the pilot of the spaceship does not know what direction the planet lies on. I am looking for the path that has the best worst-case scenario where to get to the planet, it takes the least distance compared to the worst-cases of other paths.

The question can also be worded as "Find the shortest curve in space whose convex hull includes the unit ball".

It is not proven to be the optimal path but the best solution, among the two solutions, I found is as follows:

"a shorter solution draws along an octahedron of side length $\frac{2\sqrt(3)}{\sqrt(2)}$ enclosing the unit ball. Its length is $\frac{10\sqrt3}{\sqrt2}=12.247$... If we insist on starting at the origin the length is $\frac{10\sqrt(3)}{\sqrt2}+\sqrt2=13.6616...$"

I do not get what this means at all. What kind of moves does the spaceship do to traverse the unit ball? Can someone explain to me how this solution works? Any other possible solutions are also appreciated, they do not have to be better than this one.

1

There are 1 best solutions below

0
On BEST ANSWER

The spaceship flies along the green lines in the image below, i.e., five of the edges of an octahedron.

enter image description here

The convex hull of this path is the octahedron itself and hence contains the inscribed sphere. In order to make that sphere the unit sphere, the edge length of the octahedron has to be $\sqrt 6$, so the path has length $5\sqrt 6$. Note however that we did not at the right position, i.e., to match the problem, we should add a line segment from the origin to the first vertex of the octahedron, which increases the path length to $10\sqrt 6+\sqrt 2$. (To be honest, I didn't check the computation leading to the numbers $\sqrt 6$ and $\sqrt 2$, but these should readily be verified with playing around with Pythagoras, and they are certainly plausible).


I am but not too confident how the convex hull formulation of the problem solves the original problem. Apparently, we conversely think of the planet as an unknown point on the unit sphere and the starship starts at the sphere centre (so at a known - unit - distance from the planet, but the direction is unknown). But why would travelling along a path that has the unit sphere (and hence also the planet) in its convex hull count as "finding" the planet? With the octahedral path, it may still happen that we never get closer than $\sqrt2$ to the planet (namely, if the planet is at a point where the unit sphere touches a face of the octahedron)!

Indeed, upon reading the page referenced in the OP, I notice that they discuss the problem of hitting a plane, not a planet-point. In that case, indeed, a curve visits every tangential plane to the unit sphere if and only if the sphere is in the convex hull of the curve.