Spider and fly problem on a Teserract.

Question

In the spider and fly puzzle, there is a spider on the inside of a cuboidal room wondering how it would get to a fly on another point on the inside of the cuboid. Here, we just "flatten out" the cuboid in different ways and take the shortest path across all of their shortest paths. Now, replace the cube with a Tesseract. If the spider is restricted to the cubical boundaries (it can now "fly in 3-d space") and the fly is similarly on another cubical boundary, the same algorithm can be extended. Just flatten it out in 3-d space every possible way and find the shortest straight-line path among them. But what do we do if the spider loses its new power and goes back to only crawling on the 2-d surfaces (and the fly is on one of those surfaces as well). Now the trick from before where we flatten out doesn't work anymore. It is impossible to flatten out a Tesseract onto a 2-d surface without having some faces overlap (see: Prove that it isn't possible to flatten a Teserract into 2-d space.). So what do we do now? How to find the shortest path between two points on the 2-d surfaces of a Tesseract? Is there no algorithm?

NOTE: The accepted answer here: Is there a general solution for the "Spider and the Fly Problem"? in the 3-d case does require looping through unfoldings. The unfoldings are basically spanning trees. But for a given spanning tree, not sure how to get the shortest path without being able to "lay it flat".

Answer 1

Not an answer, just a fleshing-out of my comment that is itself too long for a comment. Making it C-W in the hope of inviting others to contribute.

For simplicity, let's work in the cube $I^{n} = [-1, 1]^{n}$ in Euclidean $n$-dimensional space, whose vertices are $n$-tuples of $1$s and $-1$s. Everything combinatorial below extends with obvious modifications to a general box $$ \prod_{j=1}^{n} [a_{j}, b_{j}] = [-a_{1}, a_{1}] \times [-a_{2}, a_{2}] \times \cdots \times [-a_{n}, a_{n}]. $$

By writing $$ [-1, 1] = \{-1\} \sqcup (-1, 1) \sqcup \{1\} $$ (disjoint union, hence $\sqcup$), we may index the set of all faces by ordered $n$-tuples $(e_{j})_{j=1}^{n}$ in $\{-1, I, 1\}^{n}$. We can usefully encode incidence data by defining $$ \begin{array}{r|rrr} \cap & -1 & I & 1 \\ \hline -1 & -1 & -1 & \varnothing \\ I & -1 & I & 1 \\ 1 & \varnothing & 1 & 1 \\ \end{array} $$ and extending componentwise: $(e_{j}) \cap (e_{j}') = (e_{j} \cap e_{j}')$. An obvious modification defines containment.

• For $0 \leq k \leq n$, a $k$-face is the set of points where precisely $n - k$ coordinates are fixed and the remaining $k$ vary freely in $[-1, 1]$, namely a sequence with precisely $k$ components equal to $I$.
• Consequently, there are $2^{n-k}\binom{n}{k}$ faces of dimension $k$, parametrized by picking $k$ "free" components and setting the remaining $(n - k)$ components to either $-1$ or $1$.
• Two faces intersect if and only if the intersection of their formal representations has no "$\varnothing$" component.

The locations of a spider and a fly may be encoded as $n$-tuples $(x_{j})$ of real numbers in $I^{n}$; the smallest-dimensional containing face of each is found by setting each $x_{j}$ with $|x_{j}| < 1$ to $I$. If each lies in the $k$-skeleton (the union of faces of dimension at most $k$), a path from the spider to the fly may be constrained by permitting it to travel only in the $k$ skeleton, or not, as the case may be.

---

To finish with a couple of speculative strategies (since OP and others here are more knowledgeable about data structures and algorithms than I):

• One might prospectively calculate the distance to the fly recursively over faces, starting with the fly's lowest-dimensional containing face and extending to neighboring faces (perhaps of constrained dimension) until reaching one of the spider's containing faces. The distance function over any particular $k$-skeleton is continuous, and (without having thought too hard) looks recursively tractable. On the other hand, there are $3^{n}$ faces, so this is not an effective idea if one is really concerned with $1000$-dimensional boxes.
• The distance function on the $1$-skeleton, and a shortest path, look easy to compute. If so, that gives an upper bound on the distance. One might then recursively shorten this path by (optimally?) pushing sequences of segments into higher-dimensional skeleta, analogously to cutting diagonally across a rectangular field.

In any case, a shortest path proceeds monotonically along the displacement vector from the spider to the fly, in the precise sense that if $x(t)$ is a piecewise-$C^{1}$ shortest parametrization starting at the spider $S$ and ending at the fly $F$, then $0 < x'(t) \cdot (F - S)$ for all $t$. That may usefully constrain the types of search needed.