  Suppose an "escaping" player moves continuously at maximum speed 1 in the
interior of a region, while a "pursuing" player moves continuously at maximum
speed $r$ outside the region. For what $r$ can the first player escape the
region, that is, reach the boundary a positive distance away from the pursuing
player, assuming optimal play by both players? We formalize a model for this
infinitesimally alternating 2-player game that we prove has a unique winner in
any region with locally rectifiable boundary, avoiding pathological behaviors
(where both players can have "winning strategies") previously identified for
pursuit-evasion games such as the Lion and Man problem in certain metric
spaces. For some regions, including both equilateral triangle and square, we
give exact results for the critical speed ratio, above which the pursuing
player can win and below which the escaping player can win (and at which the
pursuing player can win). For simple polygons, we give a simple formula and
polynomial-time algorithm that is guaranteed to give a 10.89898-approximation
to the critical speed ratio, and we give a pseudopolynomial-time approximation
scheme for arbitrarily approximating the critical speed ratio. On the negative
side, we prove NP-hardness of the problem for polyhedral domains in 3D, and
prove stronger results (PSPACE-hardness and NP-hardness even to approximate)
for generalizations to multiple escaping and pursuing players.

Computational Geometry;Computer Science and Game Theory;Metric Geometry