Evacuating the ℓp Disc

Evacuation is a search-type problem where collaborating agents seek a hidden exit on some continuous domain (for example, lines, rays, graphs, polygons.) We generalize the problem of evacuating two agents in the wireless model from the Euclidean disk to any lp metric space where p ∈ [1,∞). The original problem has seen an extensive line of variations, and our study is the first to embed this evacuation in more general metric spaces. Solving an evacuation is an optimization problem that seeks to minimize the worst-case evacuation time. We show that our family of algorithms, Wireless-Searchp(φ), is optimal for p ∈ [1,2] if φ = 0, and for p ∈ [2,∞) if φ = π/4. Our proof of optimality reduces to a novel observation in convex geometry on the relationship between chord and arc lengths on lp disks.