The Topology and Dimensionality of Pursuit Evasion

30 concepts14 papers

Imagine playing a high-stakes game of tag inside a complex maze. Intuitively, your ability to catch an evader depends on your speed and agility. However, geometric and topological research reveals a deeper truth: speed is secondary to the structure of the environment.

In multi-agent pursuit-evasion games, the number of pursuers required to guarantee capture is fundamentally dictated by the topology and dimensionality of the space. By analyzing how holes, boundaries, and higher dimensions alter an evader's freedom of movement, researchers have mapped out the exact mathematical boundaries between guaranteed capture and infinite evasion.

The Geometry of the Loop: Why Holes Demand More Pursuers

In a perfectly open, simply connected 2D environment, finding and catching an evader is straightforward. As shown by Guibas et al., the number of pursuers needed to clear a polygonal space using line-of-sight visibility scales logarithmically with the number of environmental edges. However, the moment internal obstacles—or "holes"—are introduced, the environment becomes multiply connected, and the game changes entirely.

Holes introduce a critical topological feature: closed loops. In a space with holes, an evader can exploit a central obstacle to loop around a pair of pursuers indefinitely. As demonstrated by Klein et al., two pursuers are mathematically insufficient to guarantee physical capture in any environment with holes. They cannot simultaneously block both directions of a loop while closing the distance.

Remarkably, adding more holes does not mean you need infinitely more pursuers. Both Bhadauria et al. and Klein et al. proved that exactly three pursuers are both necessary and sufficient to guarantee capture in any 2D polygonal environment, regardless of the number of obstacles or vertices.

The intuition behind this "magic number" lies in spatial partitioning. Two pursuers can systematically "slice" the environment to isolate a hole or restrict the evader's movement to a specific sector, effectively neutralizing the loop. The third pursuer is then free to close in and secure the capture.

   [Pursuer 1] ------ ( Obstacle / Hole ) ------ [Pursuer 2]
                            |
                     [Evader Trapped]
                            ^
                     [Pursuer 3 Closes In]

However, fine-grained geometric constraints still influence the difficulty of the chase:

  • Feature Size: Klein et al. noted that if the physical corridors or obstacles are smaller than the agents' movement step size, an evader can slip past pursuers entirely, causing the required team size to scale with the square root of the number of obstacles.
  • Obstacle Perimeters: Ames et al. showed that a single pursuer can only guarantee capture around a single obstacle if the perimeter of its convex hull is strictly bounded (less than 2).
  • Strategic Obstacles: Obstacles are not always a hindrance. Goldenberg et al. observed that high obstacle density can paradoxically simplify capture by creating dead ends that pursuers can leverage to trap an uncertain evader.

The Dimensionality Leap: Unbounded Freedom

While a team of three pursuers can conquer any 2D polygonal maze, this upper bound completely collapses when moving into higher dimensions. In two dimensions, the boundaries of a plane act as natural barriers that limit an evader's escape routes. In three or more dimensions, the evader gains extra degrees of freedom, allowing them to bypass obstacles that would have trapped them in a flat plane.

This sharp dichotomy was formalized by Gordinowicz et al. using geometric intersection graphs. The authors proved that if a graph represents connected shapes in a 2D plane, a small, fixed number of pursuers can always win. But if the shapes exist in 3D space, the evader can escape indefinitely unless the number of pursuers scales with the overall size of the graph.

We see this same topological breakdown when analyzing continuous paths. Erickson et al. studied the problem of catching an infinitely fast, "greedy" target on a closed curve. In 2D, the topology of the configuration space guarantees that a pursuer can always choose a direction (clockwise or counter-clockwise) to force a capture. But move that same curve into 3D, and the target can exploit complex spatial embeddings—such as double loops—to maintain a local distance minimum that never intersects with the pursuer, avoiding capture forever.

As dimensionality scales, the resource requirements scale linearly with it:

  • Grids: Bhattacharya et al. proved that exactly $n$ pursuers are necessary and sufficient to guarantee capture on an $n$-dimensional grid.
  • Continuous 3D Space: In continuous 3D multiplayer reach-avoid scenarios, Yan et al. established that a maximum of three pursuers are mathematically required to guarantee the capture of a single evader, demonstrating how coordination strategies must adapt when spatial safety zones expand.

Bottlenecks, Blind Spots, and Information Flow

Beyond global topology and dimensionality, the local features of an environment dictate how pursuers must coordinate their movement and manage information.

Consider a maze with intersecting corridors. As a team of pursuers sweeps through the environment, junctions represent critical topological bottlenecks. As Volkov et al. explained, when a searching frontier encounters a split point, it must divide. To prevent the evader from slipping back into previously cleared areas—a phenomenon known as recontamination—pursuers must deploy stationary guards at these junctions.

                         |  [Branch A] (Needs Guard)
                         |
[Searching Frontier] --->+--- Junction (Topological Bottleneck)
                         |
                         |  [Branch B] (Needs Guard)

Furthermore, the interaction between geometry and visibility constraints can destroy a pursuer's strategic advantage. In open space, initial spatial geometry and distance-to-boundary ratios can mathematically guarantee an evader's escape or capture, as explored by Wei et al.. But when obstacles are introduced, they create blind spots.

Huang et al. demonstrated that under non-anticipative information patterns (where the future is unknown), these blind spots force a pursuer to commit to a specific path before the evader's trajectory is fully revealed. The evader can then exploit this lack of foresight to escape dominance regions that would otherwise be completely secure.

To counter these blind spots in structured environments without deploying massive teams, pursuers must use specialized geometric trajectories. For instance, Berry et al. developed a deterministic "rook's strategy" that allows a single pursuer with limited line-of-sight visibility to systematically eliminate hiding spots and guarantee capture within monotone and scallop polygons, showing that when topology is constrained, clever geometry can still win the day.

Key Foundational Work

A Visibility-Based Pursuit-Evasion Problem (1999) — contributed 3 concept elements to this direction.
Multiple Agents Moving Target Search (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_topological_evasion_constraints_33e44ad3,
  title = {topological evasion constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/topological-evasion-constraints/rdr_33e44ad3957342b38c40f2c22194dae8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_topological_evasion_constraints_33e44ad3_v1,
  title = {topological evasion constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/topological-evasion-constraints/rdr_33e44ad3957342b38c40f2c22194dae8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake