Skip to content
Preprint

A new unconditional lower bound for shoreline search

Aug 2026 · 3 citations · 18 references
Mathematics

TL;DR

It is proved that every deterministic search path has competitive ratio at least $C_{\log}\approx 12.5937096701246675$ and Arb ball arithmetic provides a rigorous numerical enclosure of the constant.

Abstract

A unit-speed searcher starts at the origin of the Euclidean plane and must hit an unknown straight line whose direction and distance from the origin are both unknown. We prove that every deterministic search path has competitive ratio at least $C_{\log}\approx 12.5937096701246675$. The bound is unconditional: the path need not be cyclic, self-similar, spiral-like, or monotone in angle. For each projection direction, we compare the path with a zigzag obtained by sorting its alternating record turns. The resulting completion constraints are interpreted as jobs with scale-dependent deadlines and lower-bounded through a finite-window scheduling argument in logarithmic time. Averaging these directional bounds then uses the exact Euclidean velocity budget. In one dimension, the same method recovers the optimal cow-path constant $9$. Finally, Arb ball arithmetic provides a rigorous numerical enclosure of the constant.

View source

Similar papers

Preprint Sep 2026

The logarithmic spiral is optimal for shoreline search: a computer-assisted proof

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...

A. Temerev · 1 citation
Preprint Sep 2026

A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

We consider online packing of axis-parallel squares into a unit-width strip under the Tetris and gravity constraints: An incoming square must be lowered from above along a monotonic downwards path until it reaches support from below. Fekete, Kamphans, and Schweer [Algorithmica, 2014] gave an algorithm with asymptotic c...

N. Rasmussen · 0 citations
Preprint Aug 2026

Partial Optimal Transport on the Circle for All Transported Masses in O(N log N)

PAWC is proposed: an exact $O(N\log N)$ time, $O(N)$ memory algorithm returning all $K+1$ costs, nested active sets and plans in one run, together with a single gap that is simultaneously optimal for every cardinality.

Soheil Kolouri · 0 citations
Preprint Oct 2026

The exact worst-case asymptotic rate of Nesterov acceleration for strongly convex optimization

We study Nesterov's accelerated gradient method with its standard constant parameters for smooth strongly convex optimization. We characterize the exact worst-case asymptotic factor for the squared distance to the minimizer. To this end, we construct candidate worst-case trajectories by combining planar spirals with a...

Sebastian Pokutta, Bartolomeo Stellato · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.