Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-97-14

November 1997

Asymmetric Rendezvous on the Line is a Double Linear Search Problem

Steve Alpern and Anatole Beck


We apply a new method of analysis to the asymmetric rendezvous search problem on the line (ARSPL). This problem, previously studied in a paper of Alpern and Gal, asks how two blind, speed one players placed a distance d apart on the line, can find each other in minimum expected time. The distance d is drawn from a known cumulative probability distribution G, and the players are faced in random directions.

We show that the ARSPL is strategically equivalent to a new problem we call the double linear search problem (DLSP), where an object is placed equiprobably on one of two lines, and equiprobably at positions ±d. A searcher is placed at the origin of each of these lines. The two searchers move with a combined speed of one, to minimize the expected time before one of them finds the object.

We solve the DLSP (and hence theARSPL) for the case where G is convex on its support, and show that the solution is that conjectured in a paper of Baston and Gal.

If you would like a free copy of this report, please send the number of this report, LSE-CDAM-97-14, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-171-955 7732.
Fax: +44(0)-171-955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html