Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
2  
In the set-up you've described for Q1, isn't it the case that the evader can avoid capture as long as its unit "disk" (actually a spherical cap) of next locations is not completely contained within the union of the unit disks of its pursuers' next locations? Unless I'm badly visualizing things, this is always the case when there are only two pursuers. –  Barry Cipra May 21 '12 at 14:23
    
@Barry: are you alluding to Besicovitch's famous result that in the "disk", the man can evade the "lion" indefinitely, though the distance between them tends to zero...? –  Suvrit May 21 '12 at 22:27
    
A tiny detail bothers me. Do you mean: For each $t \in \mathbb{N}$, the evader jumps from $v_t$ to $v_{t+1}$, and then the pursuers jump from $p_t,q_t$ to $p_{t+1},q_{t+1}$? Otherwise randomness on the part of the evader would (with probability $1$) prevent $p_t=v_t$ and $q_t=v_t.$ –  Aaron Meyerowitz May 22 '12 at 9:12
    
@Aaron: You are correct, the pursuers jump after the evader does, and with full knowledge of $v_{t+1}$. I added the key "then" to the description. Thanks for catching that! –  Joseph O'Rourke May 22 '12 at 11:12

2 Answers 2

up vote 6 down vote accepted

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?

share|improve this answer
    
@Anton: Beautiful argument! If I understand it, it has broad applicability, just requiring the manifold to be closed and to have geodesics everywhere. –  Joseph O'Rourke May 21 '12 at 19:15
    
Yes, but I am not sure what do you mean by "have geodesics everywhere". –  Anton Petrunin May 22 '12 at 8:33
    
@Anton: I was (needlessly) worrying about e.g. punctures in the manifold. –  Joseph O'Rourke May 22 '12 at 11:28
    
@Anton: To clarify the discussion by unknown & Barry, could you elaborate on the "finally zero" issue? –  Joseph O'Rourke May 23 '12 at 18:01
1  
@Joseph: The job is done. –  Anton Petrunin May 23 '12 at 18:33

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).

share|improve this answer
    
@unknown: Here is my interpretation of Anton's idea. First just consider one pursuer $p$. If $v$ stays on the great circle through them, $p$ remains the same distance from $v$. But if $v$ steps off that great circle, $p$ can get a little closer (by the triangle inequality). Now the idea is for $q$ to interfere with that great circle, forcing $v$ to step off it, and so allowing $p$ to reduce the distance $|p-v|$. –  Joseph O'Rourke May 23 '12 at 12:18
    
@Joseph O'Rourke. Yes, I understood so far. The distance $|p-v|$ will be reduced but will never be $0$. –  Luc May 23 '12 at 14:05
    
@unknown: Certainly the limit is zero. I will have to think if Anton's "finally zero" can be justified... –  Joseph O'Rourke May 23 '12 at 14:51
2  
@Joseph, I agree with unknown (and had meant to raise the point myself, so my thanks to unknown for chiming in). It looks to me that two pursuers can get the limit to be 0, but the evader can always keep the distance positive. So either you want to equip each pursuer with an epsilon-sized butterfly net, or you need three pursuers. –  Barry Cipra May 23 '12 at 15:04
1  
FWIW, here's the relevant passage from David Slavitt's translation of Ovid: He [Apollo] followed, running as fast as he could // and seemed to catch up -- as a whippet races a scampering hare // across an open field and almost has it, but then // it feints and cuts to one side or the other, the snapping teeth // of the dog grazing its heels but closing somehow on air. // So it was with them, the girl and the god behind her. –  Barry Cipra May 23 '12 at 19:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.