Is there a general solution for the "Spider and the Fly Problem"?

(I would be appreciative if somebody could give a more formal formulation of this problem.)

The Spider and the Fly Problem is a problem in which the objective is to minimize the distance the spider must travel to reach the fly on the other side of the room.

The spider can only move on the surface of the room. Let S be the point where the spider is, and F be the point where the fly is. One is given the length of YG, GF, PH, and HS, as well as the length, width and height of the rectangular prism. Assume that the fly and spider stay on their respective sides, but aside from that, their points are not necessarily where they are placed on the diagram. Is there a general formula for calculating the shortest distance between the spider and the fly? (Is there a general formula for the geodesic of the cuboid?)

I solved the original spider and the fly problem (by just creating meshes of the cube and getting lucky), but I don't see how I could generalize the result, especially as the spider and fly do not have to be at the same position they are in the original problem. In the original problem, the spider is centered and one unit from the top, and the fly is centered and one unit from the bottom. I've tried considering the simpler case where the fly and spider remain in the same spot, but I still couldn't generalize it, especially for more extreme cases (if we make the height very large compared to the others, our line will go off the mesh, I'm not sure how to deal with this.)

I looked online for any hints about the problem, and the the Mathworld Page used the word "geodesic" to describe the solution. I did some more research, but could only find solutions for the sphere and some other 3d shapes. I also couldn't find any page describing a general solution to the problem, only pages using the meshes of the rectangular prism as a solution.

Solution 1:

Here's a sketch of a comprehensive solution. I doubt a simple closed-form formula can exist, if that's what you're looking for.

Consider the sequence of faces that the optimal path travels over. Every pair of consecutive faces has a common edge, so the entire sequence can be "unfolded" into the plane. For the path to be optimal, it must be a single straight line that lies entirely inside the unfolded faces.

There are only finitely many different unfoldings of the room, which correspond to different spanning trees of the adjacency graph of the room's faces (in this case, the octahedral graph). For each one, see if the line segment joining the unfolded positions of the spider and the fly lies entirely inside the unfolding; if so, record its length. Try all possible unfoldings, and keep the path with the shortest length.

This algorithm works for arbitrary polyhedral rooms. Edit: Well, perhaps not naively (see Namiki's counterexample), but if you interpret "lies entirely inside the unfolding" as "does not leave any face by crossing a edge that has been cut", then it should still work.

Solution 2:

This might be stupid, and I have no proof for this yet, but I think this would yield the correct solution and would be relatively simple to express.

Consider the faces of the cuboid. For each point inside the cuboid, assign the label of the closest face(s). Points with exactly two labels lie on a planar interface, and points with more than two labels lie on a linear interface.

Well, this is just a way to see it, but what I'm getting at is that you obtain a cuboid made of four equal toblerons which basis are the "length faces" (rectangles), and two pyramids which basis are the "front and back" faces (squares). If the length of the cuboid is lesser than the side of the square, then you obtain four toblerons and two trapezoids with square basis.

Each pyramid/trapezoid and tobleron corresponds to a unique face, and we can associate each interface with at least an edge.

Next, draw the segment SF, and mark its intersections with interfaces between pyramid/tobleron inside the cuboid. If there should be such intersections lying on linear interfaces (more than two labels), then the label limits "after" and "before" the intersection on the segment should allow to identify exactly one edge.

For each of these interface points, project the point to the corresponding edge, and do so on the plane or line defined by the interface itself.

I think the points that you obtain on the edges allow you to draw the optimal path. However, I'm not sure what should be done if the intersection is located on the small basis of trapezoids yet. I'm still thinking about how to prove that.

NOTE: description clarified after the comments of Rahul Narain, thanks

Solution 3:

EDIT : This solution is flawed as explained in the comment below. Still I find it interesting enough to leave it as is here.

As noted in Pavel M’s comment, the general case for an arbitrarily-shaped room can be quite complicated. In the limited framework suggested in the OP : a “cuboid mesh”-like room, however, there is a computation-free, purely geometric solution, explained below. I will show that there is always a unique geodesic, and my argument also immediately implies a formula for the minimal distance, which will be a sum of two or three square roots.

If the room were convex, the geodesics would obviously be line segments. Here our room is not convex, but we can decompose it as a union of three convex subsets (the green, red and yellow rectangles in figure 1). If the spider is not to waste time, it must necessarily walk in the green rectangle first, then cross the red one, and finally go to $F$ in the yellow one, without ever returning inside the red rectangle. It is then clear that any geodesic from $S$ to $F$ must be in fact a union of three segments, $[SA],[AB]$ and $[BF]$, as in figure 1.

So all that’s left to do is determine the position of $A$ and $B$. What solves everything is applying twice the following lemma (or rather its corollary) :

Lemma. Let $P,Q$ be two distinct points in the plane, and let $D$ be a line separating $P$ and $Q$. Consider the function $f: D \to {\mathbb R}^{+}$ defined by $f(M)=PM+QM$. Let $I$ denote the intersection point of $D$ and $[PQ]$. Then $f$ attains a global minimum at $I$, and on each half-line starting from $I$, $f(M)$ decreases strictly as $M$ approaches $I$.

Proof of lemma $f$ is a sum of two strictly convex functions and is therefore strictly convex, qed.

Corollary Let $P,Q,D,I,f$ be as above. Let $D’$ be any segment of $D$. Then $f$ has a unique minimum on $D’$, attained at the nearest point to $I$ inside $D’$.

Going back to our initial problem, there are three cases :

Case 1. The segment $[SF]$ is completely included in the room. In that case, the straight segment from $S$ to $F$ is the obvious unique solution.

Case 2. The segment $[SF]$ goes out only once of the room. In that case, we bypass the forbidden part by using the nearest corner (see figures 2.1 and 2.2). By applying the corollary twice, this is the unique geodesic from $S$ to $F$ in this case.

Case 3. The segment $[SF]$ goes twice out of the room. In that case we use both corners $A$ and $B$ (as in figure 3). By applying the corollary twice, this is the unique geodesic from $S$ to $F$ in this case.