# Rendezvous on the Line with Different Speeds and Markers That Can Be Dropped at Chosen Time
## 1 Introduction  
The problem that we discuss in this article revolves around the problem faced by two parachutists dropped from an airplane on an island and who need to rendezvous. In order to reduce the dimension of the search space, the two can move to the coastline and restrict their search by moving along the coastline. The two parachutists facing the sea can move to right or to the left. However, going to the right or the left is not a common sense of direction. In an island, depending on where the parachutists are located (north or south) a motion to the right can lead to go eastward or westward, and the two cannot agree on a common direction, for instance, by observing where the sea is flowing (as it would be possible if they were moving along a river). The distance separating them initially may not be known. To formalize the problem, the distance may be assumed a random variable or, this is the approach taken here, the distance is assumed to be bounded and an upper bound on the rendezvous time are searched for. Two novel parameters are considered for this problem. We assume that the two parachutists may move at different speeds and we assume that the parachutists can drop off a marker at the position they are and it may be subsequently found by the other as they pass by the same position. Finding the marker is very useful since it indicates in which direction to go to rendezvous with the other. More formally, we introduce a variation of the asymmetric rendezvous problem on the line that was introduced by [PERSON] and [PERSON] [1]. In the original setup, two players are placed on a line at a known distance \(D\) and move on the line to rendezvous. The player's strategies may be different and start at the same time, and both players move at the same speed \(v=1\). At the start and while moving, the players look in a fixed direction, say, right or left. The directions are chosen randomly each with probability \(1/2\). It results that players move either in the direction they look to or the other one, i.e., forward or backward. A strategy is a succession of forward and backward moves. The optimal solution of this problem is shown to be \(13D/8\). Many variations have been proposed showing that even a simple topology such as the infinite line leads to interesting problems. Among the hardest seems to be the symmetric rendezvous on the line where the two players have to play the same strategy. Partial solutions of this problem were obtained. In [2], a strategy was proposed that ensured the rendezvous time satisfied \(R\leq 5D\). Subsequent strategies were proposed in [3; 4] that used the same technique as in [2] and reduced the rendezvous timeto \(R\leq 2.28338D\) and \(R\leq 2.2091D\), respectively. Ref. [5] generalized the technique and improved the bound to \(R\leq 2.19653D\). The best known bound \(R\leq 2.1287D\) is given in [6]. Some papers deal with the problem where the initial distance between the players is unknown, see for instance [7; 8; 9; 10]. Usually, the distance is characterized by a probability function. Note that if the players use strategies tailored for a known distance \(D\) with rendezvous time \(R\) to a problem where it is only known that the distance is bounded by \(D\), then the rendezvous time for this problem is bounded by \(R\). The way time enters the game leads to relevant variations as well. The constraint that the players start at the same time may be relaxed and this leads to asynchronous rendezvous problems [11; 12]. Asynchronous rendezvous problems may assume that an adversary chooses the starting delay or the clocks are assumed to drift with different speeds. There are relations between problems where clocks drift at different speeds and ones where players move at different speed [12]. A problem where players move on the line and share similarities with the rendezvous problem is the group search problem on the line [13]. This problem is motivated by the evacuation problem where players must simultaneously gather at some point.