## CompSci 269S, Winter 2008: Theory Seminar

### May 9, 2008, 1:00pm in Bren Hall 1423

#
Offline Variants of the "Lion and Man" Problem

## authored by Adrian Dumitrescu, Ichiro Suzuki, and Pawel Zylinski

Appeared at SOCG 2007
`http://portal.acm.org/citation.cfm?id=1247069.1247085&coll=GUIDE&dl=GUIDE`
## presented by Kevin Wortman

**Abstract:**

Consider the following survival problem:Given a set of k trajectories
(paths) with maximum unit speed in a bounded region over a (long) time
interval [0,T], find another trajectory (if it exists) subject to the
same maximum unit speed limit, that avoids (that is, stays at a safe
distance of) each of the other trajectories over the entire time
interval. We call this variant the continuous model of the survival
problem. The discrete model of this problem is: Given the trajectories
(paths) of k point robots in a graph over a (long) time interval
0,1,2,...,T, find a trajectory (path) for another robot, that avoids
each of the other k at any time instance in thegiven time interval. We
introduce the notions of survival number of a region,and that of a
graph, respectively, as the maximum number of trajectories which can
be avoided in the region (resp. graph). We give the first estimates on
the survival number of the n x n grid Gn, and also devise an efficient
algorithm for the corresponding safe path planning problem in
arbitrary graphs. We then show that our estimates on the survival
number of Gn on the number of paths that can be avoided in Gn can be
extended for the survival number of a bounded (square) region. In the
final part of our paper, we consider other related offline questions,
such as the maximum number of men problem and the spy problem.