6
$\begingroup$

Question: Suppose that intelligent pursuers with speed $v<1$ are randomly scattered on the plane with area density $1/r$  ($r>0$ is distance from the origin). If you start at the origin and can move with speed 1, can you avoid getting arbitrarily close to a pursuer?

Variations:
- In $k>1$ dimensions, the analogous question would use pursuer density $1/r^{k-1}$.
- A harder version for the evader is to allow pursuers to arbitrarily place an additional pursuer each second at a distance $≥1$ from the evader (or if $k>2$, multiple pursuers $p_i$ with $Σ_i |p_i-\vec{e}|^{2-k}≤1$ where $\vec{e}$ is the location of the evader); the initial set of pursuers can then be empty without affecting the problem.

Observations

By rescaling the problem, the escape probability is the same for density $c/r$ for every constant $c>0$, and hence is 0 or 1. If the density were $ω(1/r)$, then the escape probability would be 0 since you could be encircled with arbitrarily small gaps at a sufficiently large (as a function of gap size) distance.

At density $1/r$, I conjecture you can escape since the cost of a trap appears inversely proportional to the gap size $d$, and the delay a trap causes appears proportional to the trap size. However, at $v = 1-ε$, you must sometimes swerve almost 90° to avoid the traps, but if you zigzag too much, the previous pursuers can catch up with you. Conway's angel problem has some of the similar subtleties.

If the evasion probability (for the problem as stated) is 0, then with probability 1, the pursuers can make (at time infinity) lim inf distance 0. (This is nontrivial; for example, two pursuers with speed 1 at locations (-1,0) and (1,0) can get arbitrarily close to you, but they can only choose 'arbitrarily close' once and cannot get lim inf distance 0 at time infinity.) Furthermore, in that case, since the set of points from which you can escape (in the stronger sense) is open, with probability 1 there are no starting points from which you can escape.

Other starting configurations: With the possible exception of the limiting value of $v$ (supremum of $v$ at which escape is possible), the choice of the starting configuration of pursuers is, within appropriate density parameters, irrelevant. Such configurations include $\{(0,±n) \text{ and } (±n,0): n∈ℕ^+\}$ for $v>1/\sqrt{2}$ and other configurations with $Θ(r)$ pursuers within distance $r$ of the origin that are appropriately spread out relative to $v$.
    Any configuration with $O(r)$ pursuers within distance $r$ of the origin can be emulated by a random density $1/r$ configuration at the cost of a constant density reduction (dependent on $ε$) and $ε$ speed loss. Conversely, nonrandom initial configurations with $\liminf\limits_{|\vec{r}|→∞} \frac{|\{i:\, |p_i - \vec{r}| \, < \, (v-ε)|\vec{r}|\}|}{|\vec{r}|} = Ω(1)$ ($p_i$ are initial pursuer locations) can emulate the density $Θ(1/r)$ configuration with the above cost: Given a virtual pursuer, we can treat it as an evader and capture it using $O(1)$ pursuers (dependent on $v,ε$ and generally using multiple starting locations) before it potentially gets to the player.

Escape at low densities: The best I can prove is that escape is possible at density $r^{ε-k}$ ($ε$ depends on $v$; $k>1$ is the number of dimensions). You can perturb your path (with sufficient smoothness and clearance) to avoid the first pursuer, use a smaller scale perturbation against the second one, and so on. For the naive implementation, you might have to avoid the $n$th pursuer $2^{n-1}$ times, and your clearance drops exponentially with $n$. However, by considering groups of pursuers, you can cut off a fraction at each length scale, allowing a polynomial clearance (relative to the largest perturbation scale, which can grow polynomially with time). The argument also works if new pursuers are added dynamically (at a slow and variable rate that does not upset the maximum counts at each distance scale).

Simple pursuit: I also solved the variation (simple pursuit) where the pursuers always move directly towards you; see this answer. There, the threshold density in $k$-dimensional space is $r^{-(k-1)v/(1+v)±o(1)}$; the nonlinearity in $1/r$ stems from the inefficiency at which simple pursuers surround you.

$\endgroup$

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.