Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-2004-08 April 2004

Abstract

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 two dimensional integer lattice Z² (graph paper) and their motions to horizontal and vertical directions, as in the original work of Anderson and Fekete. We mostly retain their assumption that the players start at diagonally opposite corners of one of the unit squares of the lattice, and for this case we obtain a complete list of all optimal strategy pairs for the scenarios with and without a common notion of clockwise.

A PDF file (300 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2004-08, 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)-20-7955 7732. Fax: +44(0)-20-7955 6877. Email: info@cdam.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

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