Rendezvous Search on the Line with Distinguishable Players

Abstract

Two players are placed on the real line at a distance d with a distribution F known to both. Neither knows the direction of the other, nor do they have a common notion of a positive direction on the line. We seek the least expected rendezvous time$R = R(F)$ in which they can meet, given maximum speeds of one. We consider the cases where F is a bounded, point, discrete, or finite mean distribution. We obtain upper bounds or exact values for R and in one case an optimality condition for search strategies. A connection with Beck’s linear search problem is established.