Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2004-06

April 2004

Rendezvous in Higher Dimensions

Steve Alpern and Vic Baston


Two players are placed on the integer lattice Zn (consisting of points in n - dimensional space with all coordinates integers) so that their vector difference is of length 2 and parallel to one of the axes. Their aim is to move to an adjacent node in each period, so that they meet (occupy same node) in least expected time R(n), called the Rendezvous Value. We assume they have no common notion of directions or orientations (i.e., no common notion of `clockwise'). We extend the known result R(1)=3.25 of Alpern and Gal to obtain R(2) =197/32=6.16,and the bounds 2n<R(n)<( 32n3+12n2-2n-3) /12n2. For n=2 we characterize the set of all optimal strategies and show that none of them simultaneously maximize the probability of meeting by time t for all t. This behaviour differs from that found by Anderson and Fekete, and the authors, for the related problem where the players are initially placed at diagonals of one of the unit squares of the lattice Z2.

A PDF file (316 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-06, 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.

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