Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-2004-09 October 2004

Bilateral Street Searching in Manhattan

(Line-Of-Sight Rendezvous on a Planar Lattice)

Abstract

We consider the rendezvous problem faced by two mobile agents, initially placed according to a known distribution on intersections in Manhatten (nodes of the integer planar lattice ): We assume they can distinguish streets from avenues (the two axes) but have no common notion of North or East (positive directions along axes). How should they move, from node to adjacent node, so as to minimize the expected time required to 'see' each other, to be on a common street or avenue.

This problem can be viewed either as a bilateral form (with two players) of the street searching problems of computer science, or a 'line-of-sight' version of the rendezvous problem studied in operations research. We show how this problem can be reduced to a Double Alternating Search (DAS) problem in which a single searcher minimizes the time required to find one of two objects hidden according to known distributions in distinct regions (e.g. a datum held on multiple disks), and we develop a theory for solving the latter problem. The DAS problem generalizes a related one introduced earlier by the author and J. V. Howard.

We solve the original rendezvous problem in the case that the searchers are initially no more than four streets or avenues apart.

A PDF file (394 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-09, 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 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: 08/11/05
For comments go to: http://www.maths.lse.ac.uk/webmaster.html