This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Alpern, S. Articles by Baston, V. Search for Related Content

Rendezvous on a Planar Lattice

Department of Mathematics, London School of Economics, Houghton Street, London WC2A 2AE, United Kingdom
Department of Mathematics, University of Southampton, Southampton, Hampshire SO17 1BJ, United Kingdom
s.alpern{at}lse.ac.uk
v.j.d.baston{at}maths.soton.ac.uk

We analyze the optimal behavior of two players who are lost on a planar surface and who want to meet each other in least expected time. They each know the initial distribution of the other’s location, but have no common labeling of points, and so cannot simply go to a location agreed to in advance. They have no compasses, so do not even have a common notion of North. For simplicity, we restrict their motions to the integer lattice Z² (graph paper) and their motions to horizontal and vertical directions, as in the original work of Anderson and Fekete (2001).

Subject classifications: search and surveillance: rendezvous search; games/group decisions: teams.
History: Received May 2002; revision received March 2004; accepted October 2004.