In a pursuit-evasion game, a team of pursuers attempt to capture an evader. The players alternate turns, move with equal speed, and have full information about the state of the game. We consider the most restictive capture condition: a pursuer must become colocated with the evader to win the game. We prove two general results about pursuit-evasion games in topological spaces. First, we show that one pursuer has a winning strategy in any CAT(0) space under this restrictive capture criterion. This complements a result of Alexander, Bishop and Ghrist, who provide a winning strategy for a game with positive capture radius. Second, we consider the game played in a compact domain in Euclidean two-space with piecewise analytic boundary and arbitrary Euler characteristic. We show that three pursuers always have a winning strategy by extending recent work of Bhadauria, Klein, Isler and Suri from polygonal environments to our more general setting.
Just as the proofs of were inspired by Aigner and Fromme, our proof of Theorem is inspired by those for the polygonal environment. actually give two different winning strategies for three pursuers. At a high level, these strategies progress in the same way, but the tactics for choosing paths and how to guard them are different. Herein, we adapt their shortest path strategy to our more general setting. The topological environment introduces a distinctive set of challenges to overcome. In particular, we do not have a finite set of polygonal vertices to use as a backbone for our guarded paths. Instead, we rely on homotopy classes to differentiate between paths to guard. Looking beyond the high-level structure of our pursuer strategy, the arguments (and their technical details) in this paper are wholly distinct from those found in @cite_9 , and our result applies to a much broader class of environments.
@cite_9
2029756211
Suppose an unpredictable evader is free to move around in a polygonal environment of arbitrary complexity that is under full camera surveillance. How many pursuers, each with the same maximum speed as the evader, are necessary and sufficient to guarantee a successful capture of the evader? The pursuers always know the evader's current position through a camera network, but need to physically reach the evader to capture it. We allow the evader knowledge of the current positions of all the pursuers as well-this accords with the standard worst-case analysis model, but also models a practical situation where the evader has 'hacked' into the surveillance system. Our main result is to prove that three pursuers are always sufficient and sometimes necessary to capture the evader. The bound is independent of the number of vertices or holes in the polygonal environment.