Logarithmic spiral path is best way to find unknown shoreline
The logarithmic spiral is optimal for shoreline search: a computer-assisted proof
Computational Geometry
Summary
Imagine a ship lost at sea that needs to find any straight shoreline, but doesn’t know where it is or how far. The authors show that moving along a special curve called a logarithmic spiral is the best way to guarantee finding that shore quickly compared to any other route. They prove this using computer-assisted math that checks all possible paths and confirms the spiral path’s optimality. This settles a long-standing question from earlier researchers about the most efficient search pattern.
What this means in practice
- •For autonomous marine vehicle designers: Design search routes for robots in environments where shoreline or boundaries are unknown and must be found efficiently.
- •For search and rescue planners: Develop guaranteed quickest strategies for locating unknown coastlines or boundaries during rescue missions with limited initial information.
A theory result. No direct application yet.
Authors
Alexander Temerev
Abstract
A ship starts at a point of the plane and moves at unit speed; it has to reach an unknown straight line, of which neither the distance nor the direction is known. The competitive ratio of a path is the supremum, over all lines, of the time at which the line is reached divided by its distance. Baeza-Yates, Culberson and Rawlins conjectured that a logarithmic spiral, with ratio $C_{\mathrm{sp}} = 13.8111351794611\ldots$, is optimal. We give a computer-assisted proof. Paths are arbitrary: the distance from the start and the polar angle may both decrease. The proof lifts the set of found directions to the universal cover of the circle, where unfolding the polar angle can only increase it (Kneser-Poulsen on the line); a bookkeeping inequality with a monotone final source then bounds the covered measure by the reward of a three-state relaxed control problem, in which inward motion is an ordinary control and excursions below the guaranteed disk are impulses. An explicit $C^1$ storage function, a tensor cubic B-spline plus a closed-form term, satisfies the dissipation inequalities of that problem at the spiral's level and is tight only at the spiral; this is verified with about $10^6$ boxes of Arb ball arithmetic, an exact jet and an interval Hessian at the spiral.