# 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.

-
This paper, unfortunately behind a paywall, gives "an explicit formula for the intrinsic diameter of the surface of a rectangular parallelepiped in 3-dimensional Euclidean space". And it's a messy one, with a bunch of cases. The intrinsic diameter is the length of the longest globally-minimizing geodesic on the surface; therefore, the actual equation of a geodesic will be at least as messy, and likely more so. –  user53153 Jan 6 '13 at 2:14
@PavelM, thanks, I suspected that such a solution would be cumbersome. Still, I would like to see a general solution if possible. –  George V. Williams Jan 6 '13 at 2:47
There are only finitely many paths from one face to another. You can always "unfold" the room along each path, check the distance, and take the minimum. –  Rahul Jan 8 '13 at 2:23
When you say “their points are not fixed”, you mean the fly can move ? In that case, if the fly moves much faster than the spider, it will never get caught. –  Ewan Delanoy Jan 8 '13 at 7:26
@EwanDelanoy, no, I mean that the spider and the fly are not necessarily where I marked them in the diagram. I will edit the question to reflect that. –  George V. Williams Jan 8 '13 at 22:41

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.

-
I believe that there should be a closed-form formula : a finite min of sums of square roots. In general, it would be a pages-long and useless formula. For the cuboid, perhaps a tolerably complex formula exists. –  Ewan Delanoy Jan 10 '13 at 18:46
@George: If it is of interest, I can add some figures and examples. It is not sufficient to only consider paths traversing the fewest number of faces. Surprisingly, in a room shaped like a long narrow corridor, the optimal path may traverse five faces. –  Rahul Jan 10 '13 at 18:46
@Ewan: Sorry, that last comment wasn't directed at you. But this one is: You would have to include the condition "path lies inside unfolded faces" in your formula somehow. –  Rahul Jan 10 '13 at 18:47
@RahulNarain, I suppose this solution is sufficient, I've awarded you the bounty. –  George V. Williams Jan 13 '13 at 20:06
@George: I thought you still had a day or two left for the bounty. I haven't had time to write the formalization of the method you requested, but I'll do it in a few days. –  Rahul Jan 13 '13 at 20:09

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

-
I think you mean grow the surfaces for each face, not each edge. Also, this approach doesn't work in the case that the room is shaped like a slab with a large square floor and ceiling and four narrow rectangular walls. If the spider is somewhere in the middle of the floor and the fly in the middle of the ceiling, your method expects the spider to jump from the floor to the ceiling without passing over any of the walls. I would consider this a bad sign for the correctness of the method. –  Rahul Jan 6 '13 at 4:06
I really meant grow the surfaces for each edge, but it is equivalent to diffusing the labels of faces (see updated description). In case the length is lesser than the side of the square, yes you're right there is a problem with the above method. –  Sh3ljohn Jan 6 '13 at 15:55

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.

-
You're forgetting that the green and yellow rectangles are actually connected to the red one on all sides. In Figure 3, it would be shorter for the spider to cross the right green edge, appear somewhere in the middle of the bottom red edge, cut across north-northeast, appear at the left yellow edge, and then reach the fly. –  Rahul Jan 10 '13 at 18:19
Indeed. I suspect that this flawed solution inspired your recent answer, though. –  Ewan Delanoy Jan 10 '13 at 18:39
It reminded me to properly post the answer I had left in a comment, so yes, in a way. :) –  Rahul Jan 10 '13 at 18:41