Randall Munroe's Lost Immortals In Randall Munroe's book What If?, the "Lost Immortals" question asks:

If two immortal people were placed on opposite sides of an uninhabited Earthlike planet, how long would it take them to find each other?

After an entertaining discussion in Munroe's usual inimitable style, he concludes with the following suggestion:

If you have no information, walk at random, leaving a trail of stone markers, each one pointing to the next.  For every day that you walk, rest for three.  Periodically mark the date alongside the cairn.  It doesn't matter how you do this, as long as it's consistent.  You could chisel the number of days into a rock, or lay out rocks to plot the number.
If you come across a trail that's newer than any you've seen before, start following it as fast as you can.  If you lose the trail and can't recover it, resume leaving your own trail.

I find this algorithm very intriguing and I can almost—but not quite—recall seeing it before.  Has this problem been studied before?  In any case, my question is, can Munroe's algorithm be improved?
It may be helpful to lay down some ground rules.
Munroe considers planets with terrain (oceans, deserts, coastlines, etc.) but for simplicity let's assume a uniform sphere and an unlimited ability to leave a trail behind.  Let's also assume that there are no pre-existing markers on the sphere that allow the players to pre-arrange something like, "Let's meet at the North Pole."  Although the original question seems to specify that the players are placed at antipodes, it seems to make more sense for their starting positions to be random.  Both people have some maximum speed of travel but can choose to move more slowly than that.  Finally, I'm not sure whether it makes a difference if the players are allowed to leave arbitrary messages along the trail for the other player to read; if this possibility complicates the problem too much, I'd be willing to simplify by declaring success as soon as one player intersects the other's trail.
 A: Four observations:


*

*In the case that they are allowed to plan beforehand, person A and B could both agree to follow a random geodesic, leaving a trail. Any two geodesics are guaranteed to intersect in two points.  Person A stops and waits as soon as he returns to his starting position.  Person B starts following A's geodesic as soon as he intersects it.  The time to completion of this solution is bounded above by $\frac{3 \times \textrm{Circumference of planet}}{\textrm{Speed of players}}$.

*If you are not allowed to plan beforehand, but you can see a finite distance away, you could use the following strategy. From where you start, make a bunch of circles by slicing planes through the circle perpendicular to the radius pointing at you. Make the distance between the circles small enough that you can see from one circle to the next. Walk each circle twice, leaving the message "do not cross this circle" along each path. You should eventually trap the other player between two circles, and you will find them on the second pass around the circle.  This also works even if you are blind, as long as you can reach out a finite distance with your arms (you are not a point mass). 

*If you are not allowed to plan beforehand, you are blind, and you are a point mass, then you really have no hope.  In the worst case scenario, the other player just stays absolutely still, and you have probability zero of ever bumping into them, no matter what path you take.  Although if you are immortal I guess you could still try to approximate a space filling curve, just for fun.  Note that solution 1 works even if you are blind point masses, you just need to be able to talk beforehand.

*If you cannot write messages, or plan beforehand, I think you are also out of luck, since you could theoretically stay antipodal to each other for all time. 
A: Munroe's algorithm runs into trouble if one immortal (say, Charles) comes across the trail of the other (say, Marie) while Marie has already ran into and is following Charles' trail.  If the two have the same maximum speed, they'll chase each other forever.  You'd have to establish some rule, like one person reversing direction after a full loop, or have the strategy involve gradually cutting into and closing the circle.
I think the optimal symmetric strategy, assuming full trail and marker capability but no significant radius of sight, is to walk a random geodesic, leaving markers indicating the time since the start of the walk.  After intersection, an immortal will be able to determine who will intersect the other's geodesic first; the first to cross the other's path follows it forward, and the second turns around and meets him.  This strategy gives a worst-case end time of 1.25*(circumference of planet)/(speed of immortals).
