Introduction
The pursuit-evasion game is a classic problem in computational geometry, often modeled as a "cop and robber" scenario on a graph. This paper investigates a specific variation known as the "puppy chasing problem." In this game, a human attempts to catch a "naive" but infinitely fast puppy on a graph embedded in a 2D plane. While previous work established solutions for simple cycles, this research extends the winning strategy to more complex structures, specifically orthogonal straight-line plane graphs—graphs where every edge is either horizontal or vertical and no edges cross.
The Pursuit-Evasion Model
In this model, the puppy is characterized by its "naive" behavior. It does not plan its route to avoid the human; instead, it instantly moves to any point on the graph that locally minimizes its Euclidean distance to the human's current position. Because the puppy is infinitely fast, it can traverse any distance on the graph in zero time, provided its path doesn't pass through the human.
The challenge for the human is to find a path that eventually forces the puppy into the same location. This is non-trivial because the puppy's local minimization can lead it to "hide" in different branches of a complex graph.
Recursive Strategy for Orthogonal Graphs
The core contribution of this paper is a recursive algorithm designed for orthogonal layouts. The strategy relies on systematically "clearing" regions of the graph using a top-down approach.
The No-Jump Lemma
A critical component of the proof is the No-Jump Lemma. The authors demonstrate that if a human occupies a horizontal line $l$ and the puppy is currently below that line, the puppy cannot cross $l$ to reach a region above it unless the human moves first. This allows the human to declare the area above their current horizontal position as "forbidden" or "cleared."
Sweeping and Reduction
The human employs a "sweeping" motion, typically starting from the topmost horizontal edge. By identifying "cut edges" (bridges) and leveraging a dominance hierarchy to handle nested components, the human can prune the graph. Each step reduces the set of edges available to the puppy. Eventually, the puppy is trapped on a single segment where the human can close the distance and complete the catch.
Key Results and Future Work
The primary result is Theorem 1.1, which proves that a winning strategy exists for any finite connected graph with an orthogonal straight-line embedding. This provides a constructive and relatively simple algorithm compared to the topological methods used for simple cycles.
While the orthogonal constraint simplifies the puppy's movement patterns, the authors believe the result is more general. They propose Conjecture 1.2, stating that a winning strategy should exist for any straight-line embedding, regardless of edge angles. Proving this remains an open challenge, as the "No-Jump" logic becomes significantly more complex when edges can slant in any direction.
Summary updated