Rendezvous search when marks are left at the starting points

Leaving marks at the starting points in a rendezvous search problem may pro vide the players with important information. Many of the standard rendezvou s search problems are investigated under this new framework which we call m arkstart rendezvous search. Somewhat surprisingly, the relative difficultie s of analysing problems in the two scenarios differ from problem to problem . Symmetric rendezvous on the line seems to be more tractable in the new se tting whereas asymmetric rendezvous on the line when the initial distance i s chosen by means of a convex distribution appears easier to analyse in the original setting. Results are also obtained for markstart rendezvous on co mplete graphs and on the line when the players' initial distance is given b y an unknown probability distribution. (C) 2001 John Wiley & Sons, Inc.