← All papers
First page of Optimal Patrol Widths in the Infinite-Corridor Barrier-Guarding Game

Optimal Patrol Widths in the Infinite-Corridor Barrier-Guarding Game

Kevin M. Boergens

math.OC Nov 19, 2026 · v1 math.MG
An accompanying Lean 4/Mathlib library formalizes wall-budget algebra, excursion inequalities and a root bracket, and kernel-replays the rational surface and continuum certificates.
A guard of speed at most one and capture radius $r$ patrols an infinite corridor. An intruder knows the patrol and can follow any path of speed at most $q$ from one end to the other. We determine where the maximum width permitted by straight wall runners can be guarded against all such paths. Write $W_{\mathrm{opt}}(q)$ for the supremum over patrols with bounded longitudinal excursion and $F(q)=2r\sqrt{1+(3q^2+2q-1)^{-1}}$ for the wall ceiling on $1/3 < q < 1$. A four-leg bowtie attains $F(q)$ exactly for $q_a\le q < 1$, where $0.457892036651 < q_a < 0.457892036652$. For every $1/3 < q < q_a$ the supremum is strictly smaller. As $q$ approaches $q_a$ from below, $F(q)-W_{\mathrm{opt}}(q)$ is bounded above and below by positive constant multiples of $r(q_a-q)^2$. The lower estimate controls near-optimal patrols uniformly in their period. A rescaled bowtie gives the matching upper estimate. We also prove that periodic patrols give the same supremum as bounded-excursion patrols. For $q\ge1$ the one-way optimum is $r\sqrt{4+q^{-2}}$, a transverse sweep. This sweep is optimal against transit in both directions for $q\ge1/2$. At low speeds, $qW_{\mathrm{opt}}(q)/r$ tends to two, and an explicit ten-leg patrol guards width greater than $(2/q-1.235353)r$ throughout $0 < q\le1/40$. Rational spacetime and flux certificates give finite-speed bounds, including $6.944691333740r < W_{\mathrm{opt}}(1/4)\le8.10r$.

A guard with unit speed and capture radius r patrols an infinite corridor against an intruder of speed q who knows the patrol. The problem is to find the maximum corridor width W_opt(q) that some patrol can guard against all transit paths.

A wall-phase ceiling F(q) is derived for 1/3<q<1 by mapping patrols onto a Euclidean phase cylinder. Barrier and wavefront separators then show that four-leg bowtie patrols attain this ceiling. Strict loss below a diffraction threshold q_a is proved, and exact rational spacetime-surface and flux certificates give bounds at finite speeds. Parts of the algebra and all certificates are replayed in Lean 4 with Mathlib v4.15.0.

The bowtie attains F(q) exactly for q_a≤q<1, with q_a≈0.457892036651. Below q_a the gap is of order r(q_a−q)^2, and the transverse sweep r√(4+q^{-2}) is optimal for q≥1. Certified bounds include 6.9447r < W_opt(1/4) ≤ 8.10r, together with low-speed asymptotics.