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.
More recently, an analogous result was proven by Bhadauria, Klein, Isler and Suri @cite_9 for pursuit-evasion games in a two-dimensional polygonal environment with polygonal holes. In this turn-based game, an agent can move to any point within unit distance of its current location. Like Aigner and Fromme, they use colocation as their capture criterion. prove that three pursuers are sufficient for pursuit-evasion in this setting, and that this bound is tight. The pursuer strategy is inspired by the Aigner and Fromme strategy for planar graphs: two pursuers guard paths that confine the evader while the third pursuer takes control of another path that further restricts the evader's movement. Of course, the details of the pursuit and the technical proofs are quite different from the graph case. Their proofs make heavy use of the polygonal nature of the environment, both to find the paths to guard and to guarantee that their pursuit finishes in finite time.
@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.