AI Proof WatchKeep up with AI contributions

Optimal competitive ratio for straight-shoreline search

A searcher follows a planar path without knowing the location or direction of a straight shoreline. What path minimizes the worst-case ratio of distance traveled before reaching it to the shoreline’s distance from the start?

Why it matters and what counts as progress

Why it matters: An optimal ratio would solve a geometric online-search problem with no directional information.

What counts as progress: A lower bound matching the logarithmic spiral’s ratio about 13.8111351794611, covering paths with decreasing radius or reversing polar angle, or a path with a smaller ratio.

How the problem developed

  1. 1993 · Problem formulation [1]

    Ricardo A. Baeza-Yates, Joseph C. Culberson and Gregory J. E. Rawlins Framed planar search with an unknown straight shoreline and proposed the logarithmic spiral with competitive ratio about 13.811 as the natural candidate.

  2. 12 Aug 2026 · Lower bound [2]

    Alexander Temerev Proved an unconditional lower bound of 12.5937… for every deterministic path, without assuming the path is cyclic or spiral-like.

  3. 21 Sept 2026 · Computer assisted proof [3]

    Alexander Temerev Reported a computer-assisted proof that the logarithmic spiral, with ratio 13.811135…, is optimal among arbitrary paths.

AI contribution

Sources

  1. Ricardo A. Baeza-Yates, Joseph C. Culberson and Gregory J. E. Rawlins, Searching in the Plane (1993)
  2. Alexander Temerev, A new unconditional lower bound for shoreline search (2026)
  3. Alexander Temerev, The logarithmic spiral is optimal for shoreline search: a computer-assisted proof (2026)
  4. Original paper and AI contribution disclosure
Website timeline

Publication dates and editorial changes.