Question

I know pursuit-evasion has been studied in many contexts, including on a manifold (e.g., Melikyan, "Geometry of Pursuit-Evasion Games on Two-Dimensional Manifolds"), but I have not seen this version:

There is a pursuer, a point $p_t$ at time $t$, while the evader is at $v_t$. They start at $p_0$ and $v_0$. For each $t \in \mathbb{N}$, the evader jumps from $v_t$ to $v_{t+1}$, and then the pursuer jumps from $p_t$ to $p_{t+1}$. Both jumps are at most a unit distance, measured by shortest path on the manifold $\cal{M}$. Both pursuer and evader know the other's location at all times. The evader is captured if $p_t = v_t$ at some time $t$.

Let $\cal{M}$ be a sphere. Then the pursuer might fail to capture the evader, who can just run away on a great circle. But what if there are two pursuers, $p_t$ and $q_t$? Specifically:

Q1. For $\cal{M}$ a sphere, can an evader always be captured by two pursuers initially at the north and south poles?

There is a general principle for $\cal{M}=\mathbb{R}^n$: it suffices for the evader to be inside the convex hull of the pursuers (e.g., Kopparty, Ravishankar, "A framework for pursuit-evasion games in $R^n$," Information Proc. Lett., 2005). It seems a natural extension that two antipodal pursuers on a sphere suffice.

Q2. For $\cal{M}$ a surface homeomorphic to a sphere embedded in $\mathbb{R^3}$, with metric inherited from the Euclidean metric in $\mathbb{R^3}$, will placing $p_0$ and $q_0$ at points realizing the diameter of $\cal{M}$ suffice to capture any evader? (By diameter here I mean that the shortest path from $p_0$ to $q_0$ on the surface is maximum over all pairs of points on $\cal{M}$.)

This is much less clear to me. A counterexample would be interesting. But if the answer to Q2 is Yes, I would be interested to learn if there are closed, bounded surfaces of higher genus for which just two well-placed pursuers suffice.

The literature on pursuit-evasion is vast, and I suspect the answers to my questions are known. Thanks for suggestions or pointers!

Answer 1

My original answer was wrong, here I summarize the discussion in the comments, mostly by Barry Cipra .

Q1. On the round sphere, 3 pursuers can catch the evader the following way. If one pursuer starts from the pole then he can move staying on the same meridian, as the evader and keeping him on a larger distance from the pole. Moreover while doing all this the pursuer can converge to the equator. Now let us apply the same strategy for three poles on the same distance on some equator $E$, this will make the evader to run into one of the poles for $E$, and the pursuers will appear very close from three sides on angle near $\tfrac23\cdot\pi$ to each other. The next step the game is over.

If the equator has length $> 4$ then 2 pursuers is not enough. The evader can allways jump in the direction with angle $\ge \tfrac\pi2$ to each of the pursuers. They can not get him, but one of them can get as close as he wants. Moreover this can be done on any closed Riemannian manifold of arbitrary dimension.

Indeed, assume that the first pursuer always jumps by $1$ in the direction of the evader. If the distance between evader and pursuer stays bounded below by some positive number then the trajectory has to be closer and closer to a geodesic; say $$\angle v_{n-1}v_nv_{n+1}\to\pi\ \ \text{as}\ \ n\to\infty.$$ If the manifold is closed then it is possible to predict the position of evader with great accuracy unless the distance from the first pursuer to the evader, say $d$, gets smaller in $(1-\varepsilon)$ times for a fixed $\varepsilon>0$.

The second pursuer can appear in such places in advance and wait, either he catches the evader or makes $d$ smaller in $(1-\varepsilon)$.

About Q2. Maybe an interesting question is: Given a positive integer $n$, is it possible to construct a Riemannian metric on the spahere so that $n$ pursuer can not catch the evader?

Answer 2

I don't have enough reputation to comment. So I apologize that I write this as an answer. I don't understand the answer of Anton Petrunin. According to it, two pursuers are enough to capture an evader in the sphere. But as Barry Cipra said in the comments, actually the opposite is true: the evader is always able to escape (just consider the great circle through the two pursuers and the hemisphere defined by it containing the evader. The evader just have to go so close to the center of this hemisphere as possible. The pursuers won't be able to reach him.)

On the other hand, I actually like to think of two antipodal points in the sphere as a convex subset (convex meaning that any two points in the subset at distance $<\pi$ are connected by a geodesic). Thus the analogy with the cited paper won't apply (one needs three or more pursuers).