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.

  • $\begingroup$ Is the goal of the evader to evade infinitely long or to escape the polygon? $\endgroup$ Jun 28, 2020 at 23:06
  • $\begingroup$ @VarunVejalla Indefinitely escape $\endgroup$ Jun 29, 2020 at 4:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.