Abstract
We study a pursuit-evasion game in which one or more cops try to capture a robber by moving onto the robber's current location. All players have equal maximum velocities and can observe each other at all times. We show that three cops can capture the robber in any polygonal environment, even those containing a finite number of holes (obstacles).
Introduction
The "Cops and Robbers" game is a classic problem in computer science and mathematics. While it is well-understood on graphs—where it is known that three cops can catch a robber on any planar graph—translating this to a continuous 2D environment like a building floor plan is surprisingly difficult. The core challenge lies in discretization. Simply overlaying a grid on a polygon fails because a robber in continuous space isn't restricted to grid vertices; they can move between them, potentially evading capture indefinitely if the grid is too coarse. Furthermore, making the grid fine enough to approximate continuous motion leads to an explosion in state space, making algorithms prohibitively slow.
This paper seeks a purely geometric strategy that works in continuous space and whose complexity depends on the number of corners (vertices) in the environment, rather than the resolution of a grid.
Methodology: Slicing and Guarding
The authors propose a recursive strategy where three cops coordinate to shrink the "safe" area available to the robber. Their approach relies on three primary types of maneuvers:
- Guarding a Shortest Path: A single cop can "guard" a shortest path between two points. Once a cop is in position, if the robber tries to cross that path, they will be captured.
- Obstacle Moves: If the robber is near a hole (obstacle), the cops use a shortest-path maneuver to "attach" their guarded boundary to the obstacle, effectively removing that obstacle from the robber's reachable area.
- Slicing Moves: When no obstacles are immediately reachable, the cops use a "slicing" technique. Two cops guard two paths that trap the robber in a sub-region. The third cop then creates a new "slice" (a third shortest path) that further bisects this region.
This strategy is designed to be invariant-maintaining: after every round of moves, the number of vertices or obstacles in the robber's restricted area strictly decreases.
Key Insights and Ideas
The Power of Three
The jump from two to three cops is critical. While one cop can guard a path and two can capture a robber in a simple polygon (no holes), the third cop acts as the "swinger." This allows the team to redefine the boundaries of the search space without letting the robber escape through a hole.
Topology Simplification and Funnels
Instead of trying to "chase" the robber in a traditional sense, the cops perform "topological surgery." They treat the environment as a set of vertices and holes, systematically reducing the complexity of the robber's world until it becomes a "simply-connected" polygon (one with no holes), at which point capture is trivial.
A key geometric tool in this proof is the funnel structure. Funnels are mathematical structures formed by shortest paths in polygons. The authors utilize these to prove that there is always a way to place a third path that touches an obstacle or reduces the vertex count.
Key Results
- The Three-Cop Theorem: The paper formally proves that three pursuers with equal maximum velocity can capture an evader in any polygonal environment with a finite number of holes.
- Finite Time Capture: The strategy is guaranteed to result in capture within a finite number of steps. Specifically, the number of "rounds" required is bounded by the number of vertices in the environment.
- Efficiency: The algorithm's complexity is proportional to the geometric parameters (the number of vertices $n$), making it much more efficient than grid-based discretization methods.
Limitations and Future Work
While this result is a significant theoretical milestone, it assumes "perfect information"—the cops always know exactly where the robber is. In many real-world robotics scenarios, visibility is limited by walls. Furthermore, the paper assumes players can change direction instantly (holonomic motion), which does not account for the physics of actual robots or vehicles with turning radii. Future research may explore "visibility-based" pursuit where the robber's location is only known when in line-of-sight, a scenario that would likely require more than three cops.
Summary updated