6
$\begingroup$

Assume $n$ pursuers ($P_i$) at the vertices of an $n$ sided regular polygon with the evader ($E$) at the centre. For what all $n$ can be the evader be caught? Pursuers and evader have same speed

For $n≥3$, pursuers win. Consider the case with $3$ pursuers. Consider the equilateral triangle whose midpoints are given by the initial positions of the pursuers. Each pursuer simply moves along their side of this triangle as per the projection of the evader along that side. ($P_i E$ is perpendicular to side and $P_i$ lies on side). Since there will be leftover scope for movement, shift one of the sides closer while maintaining it parallel. The triangle will no longer be equilateral but its angles will still be $60$ degrees. Repeat until triangle becomes point sized.

In worst case this requires pursuers to move $2\Delta x + \epsilon$ for every $\Delta x$ of evader movement ($2\Delta x$ to maintain the perpendicular condition for all three sides, and $\epsilon$ additionally to shift a side). What if we were restricted to $\Delta x$ movement?

Assume $n$ pursuers on the vertices of an $n$ sided polygon and a single evader at the centre. Pursuers must move such that the sum of their speeds (absolute) does not exceed the evader's speed. For what all $n$ can the evader be caught?

A practical case where this situation might occur is where play is turn by turn. Consider the version discrete in time and space, where on each turn - exactly one pursuer can move one unit and the evader can move unit.

How can this be solved? I tried writing a simulation for it using some intuitive strategies - in all cases the evader won. Is there any existing work where this problem has been solved? It seems like a useful base case to tackle before dealing with harder $n$ pursuer $m$ evader problems.

$\endgroup$
4
  • $\begingroup$ Is the goal of the evader to evade infinitely long or to escape the polygon? $\endgroup$
    – Varun Vejalla
    Commented Jun 28, 2020 at 23:06
  • $\begingroup$ @VarunVejalla Indefinitely escape $\endgroup$
    – ghosts_in_the_code
    Commented Jun 29, 2020 at 4:55
  • $\begingroup$ Regarding the initial problem it is important to specify that the persuer collaborate as a team (there is one player that decided the moves of all of them). In contrast if each persuer was following its self-interests of catching the evader himself, it would be a quite different game. (And perhaps the evador could escape.) $\endgroup$
    – Pavel Kocourek
    Commented Dec 30, 2022 at 0:57
  • $\begingroup$ I would start analysing this problem by considering the game between $E$ that wants to cross the line between a pair of pursuers. The first observation should be that once $E$ is outside of the convex combination of points $\{P_i\}_i$, then $E$ can evade. $\endgroup$
    – Pavel Kocourek
    Commented Dec 30, 2022 at 1:35

0

Reset to default

You must log in to answer this question.