Algorithm for people to congregate with limited relative location information

Question

(If you have a good edit for the title, please comment so I can change it.)

I saw this problem a while ago and I can't seem to figure it out:

Some paratroopers jumped on an infinite plane and when they hit the ground, they were all dazed and passed out. After a while, the paratroopers begin to wake up at random times. They could all wake up very quickly or take a very long time. Eventually, they will all wake up, but for any time $t$ it's possible that a paratrooper will wake up after that time. Each paratrooper has a map that has the position of all the paratroopers. When a paratrooper wakes up, he activates the map to locate the other paratroopers, but it works only for a split second, so he can see the location of all other paratroopers but not the direction of their motion. It is pitch dark, so the paratroopers can't see anything around them. What is the strategy the paratroopers can adopt if they wish to congregate within $\varepsilon$ of each other, for an arbitrarily small $\varepsilon$?

Clarification: The paratroopers can only see others relative to each other, they cannot tell direction (i.e., East-West, etc.).

Answer 1

Here is one solution (though maybe not the intended one):

You can designate one guy as the meeting point. That guy does not move at all, and all others come to him. How do you designate the guy? simple: just choose the one who landed farthest to the east. Using the GPS should tell you wether you are the one or not.

Answer 2

another approach:

Construct a Minimum spanning tree of the positions. Then start from the leaves of the tree, picking up (and possibly waking up) people on the way. (So if you are not on a leaf-node, you are not allowed to move until you are picked up by people coming from the leaves.)

I dont think this is the intended way (probably @MikeEarnest has the "correct" solution), but I thought it was fun :)

Answer 3

I will assume that two paratroopers can "see" each other once they are at same location. I think this assumption is necessary for the problem to be solvable for two paratroopers; the strategy in that case is they head to each other's location, stopping when they bump into the other.

The best I can do is two solutions which each work with some mild sounding additional assumptions.

---

Here is a solution which works if the pairwise distances between the landing locations are distinct.

When you wake up, compute the distances between all pairs of paratroopers, and let A and B be the closest pair. If you are neither A nor B, do not move until they come to you.

A and B will first find each other by heading to each other's location, meeting somewhere on the line segment connecting them. Once they bump into each other, they will repeatedly head towards the closest of the currently unfound paratroopers, and wait for them to wake up.

If you are not A or B, then once A and B arrive at your location, you join the growing search party, heading towards the next closest unfound trooper.

---

Here is a solution which works as long as the paratroopers can make random decisions:

When you wake up, memorize the $n$ current locations $p_1,p_2,\dots,p_n$ of all the paratroopers, including yourself. Repeatedly choose one of the $n$ points randomly, head to the chosen point, and wait there for a random amount of time (namely, repeatedly flip a coin, and wait for one hour each time the coin is heads, stopping when you first get tails). If at the end of your waiting period, all other paratroopers are present, stop.

Since the paratroopers are moving around and wake up at different times, they will all compute different sets of locations $p_1,\dots,p_n$. However, they will all have at least one location in common. Namely, if $A$ is the last paratrooper to wake up (or even tied for last), then everyone's list will include the place where $A$ landed. Since at any point in time there is a positive probability that everyone will head to location $A$ and wait there long enough for everyone else to arrive, the laws of probability guarantee it will eventually happen.

---