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.
The classic paper of Aigner and Fromme @cite_1 initiated the study of multiple pursuers versus a single evader on a graph. In this turn-based game, agents can move to adjacent vertices, and the cops win if one of them becomes co-located with the robber. This paper introduced the cop number of a graph, which is the minimum number of pursuers (cops) needed to catch the evader (robber). Aigner and Fromme proved that the cop number of any planar graph is at most 3. This bound is tight, as the dodecahedron graph requires three cops. At a high level, their winning pursuer strategy proceeds as follows. Two cops guard distinct @math -paths where @math are vertices of the graph @math . This restricts the pursuer movement to a subgraph of @math . The third pursuer then guards another @math -path, chosen so that (1) the robber's movement is further restricted, and (2) one of the other cops no longer needs to guard its path. This frees up that cop to continue the pursuit. This process repeats until the evader is caught.
@cite_1
2046635105
Let G be a finite connected graph. Two players, called cop C and robber R, play a game on G according to the following rules. First C then R occupy some vertex of G. After that they move alternately along edges of G. The cop C wins if he succeeds in putting himself on top of the robber R, otherwise R wins. We review an algorithmic characterization and structural description due to Nowakowski and Winkler. Then we consider the general situation where n cops chase the robber. It is shown that there are graphs on which arbitrarily many cops are needed to catch the robber. In contrast to this result, we prove that for planar graphs 3 cops always suffice to win.