Source-linked AI summary
Bellman Search in Arbitrary Finite Dimension: A Self-Similar Cell Theorem and Effective Computability of Planar Shoreline Search
Florentin Koch
TL;DR
The paper asks how shoreline-search paths against unknown affine lines can be reduced from infinite histories and continuous curves to finite, certifiable objects. It proves a self-similar cell reduction, makes the reduction effective, and concludes that the optimal deterministic planar Shoreline value C*_2 is computable.
Problem
Shoreline search requires a path from the origin to meet an affine line whose normal and distance are unknown, while effective control of the finite cell needed for computation remains necessary.
Method
The paper uses quasi-returns and max-memory to extract a self-similar cell, bounds its scale, length, and vertices computably, then applies support functions, polygonalization, and quantifier elimination.
Results
The optimal deterministic planar Shoreline value C*_2 is effectively computable, with certified rational intervals obtainable at any prescribed precision.
Takeaways & Limitations
Every admissible finite-ratio history can be approximated with arbitrarily small loss by repetitions of one homothetic cell, enabling a finite decision procedure for planar Shoreline search.
Takeaways & Limitations
The reduction does not impose a spiral or polygonal form on the extracted cell, and the computability conclusion is qualitative rather than practical because covering bounds and quantifier-elimination complexity are extremely large.
Abstract
from arXiv · showhide
A shoreline-search path starts at the origin and must meet an unknown affine line, without knowing either its normal or its distance. We first establish a self-similar reduction theorem for homogeneous search problems whose historical information is a record profile updated by pointwise maximum. Two quasi-returns of the normalized state delimit a block that renews the required profile by itself; a short connector closes this block into a cell. Every finite-ratio path can therefore be approximated, with arbitrarily small loss, by repetitions of a single cell at all scales. The main chain is then made effective. A finite coding of the state space computably bounds the scale factor and normalized length of a nearly optimal cell. For planar Shoreline search, the support function of the convex hull gives an exact cell functional. A one-sided polygonalization then reduces the problem to a computable number of vertices, after which quantifier elimination decides whether a polygonal cell exists below a rational threshold. It follows that the optimal deterministic planar Shoreline value $C_2^*$ is a computable real: for every rational $ε>0$, an algorithm terminates with a rational interval of width at most $ε$ containing $C_2^*$. Additional results---sliding memory, Bellman transitions, deadlines, geometric filters, and relative equilibria---are presented separately as a toolbox for certified computation and for the study of spiral rigidity; they are not used in the computability proof.
1 Introduction
The paper studies deterministic Shoreline search against an unknown affine line and develops a five-link route from self-similar cells to effective computation of the planar optimum.
- 1.1 The problem and the main result: A Shoreline strategy is a locally rectifiable arc-length path from the origin, while the adversary selects an unknown unit normal and distance.The target line is determined by the pair (u, D), with u ∈ S1 and D > 0.
- 1.1 The problem and the main result: The paper uses a purely multiplicative competitive ratio at every target distance, excluding additive constants and minimum-distance variants.These alternative conventions are explicitly outside the proofs.
- 1.3 Contributions and logical status of the results: Every finite-ratio admissible history can be replaced, with arbitrarily small loss, by repetitions of one homothetic cell at all scales.The reduction extracts a cell from an otherwise unrestricted path rather than prescribing its inspection curve in advance.
- 1.4 Overview of the proof: Finite coding of normalized states and a counted pigeonhole argument computably bound the return index, scale factor, and normalized length of a nearly optimal cell.This effectivizes the self-similar reduction at fixed precision.
- 1.4 Overview of the proof: Support functions and a centered inradius yield an exact cell functional, while one-sided chord replacement produces a polygonal cell with a computable vertex bound.The continuous curve is thereby reduced to finite geometric data before decision procedures are applied.
- 1.4 Overview of the proof: Quantifier elimination decides whether a polygonal cell meets a rational threshold, and rational bisection then returns a certified interval for the planar optimum.The resulting algorithm terminates with an interval of prescribed width containing C_2^*.
3 Normalization and quasi-returns
Normalized states remove absolute scale while retaining cost, position, and historical records. Precompactness yields arbitrarily distant quasi-returns; max-memory renews the intervening profile, and a connector turns the block into a repeatable cell with arbitrarily small loss.
- Normalization retains cost, position, and all records while quotienting out absolute scale.
- Precompact normalized states guarantee arbitrarily accurate quasi-returns with arbitrarily large index gaps.
- The admissibility hypotheses require closure under restriction, concatenation, scaling, reparametrization, max-law records, and normalized-state precompactness.
- Max-memory forces the intermediate block between a quasi-return to recreate the required dilated profile by itself.
- A short connector closes the block into a finite cell, while the geometric past contributes finite cost L/(Q−1).
- As the return error decreases and the scale gap grows, the repeated cell’s ratio approaches the original history’s ratio.
- The reduction preserves value but imposes no spiral or polygonal form on the extracted cell.
5 Effective return and a uniformly bounded cell
The finite self-similar reduction becomes effective by coding normalized states and applying a counted pigeonhole argument. This yields computable bounds on return location, scale factor, and normalized cell length at fixed precision.
- Theorem 4.1 leaves the quasi-return index unbounded, so computability requires a uniform computable rank bound.
- Every bounded-ratio hyperplane-search path in ℝ^D admits an extracted cell between computably bounded levels.
- The cell’s scale factor and length normalized by the initial level are bounded by computable functions of (D, U, ζ, λ).
- A finite code for normalized states makes sufficiently close repeated codes, and hence suitable returns, computably identifiable.
- The connector contributes less than ζ/16, giving a resulting cell ratio below CR(γ)+ζ.
- These bounds control scale span and length but do not yet bound the number of turns; polygonalization supplies that later.
6 Abstract scope of the reduction
The reduction applies beyond Euclidean plane search: compact symmetries yield equivariant cells, and proper metric-cone geometry verifies the hypotheses in finite-dimensional normed spaces. For hyperplane search, nearly optimal homothetic cells follow.
- Compact isometry groups extend self-similar reduction from pure scaling to cells repeated under combined scaling and symmetry.
- In the plane, SO(2) produces direct similarities and connects the reduction to relative equilibria.
- For proper metric cones with continuous degree-one homogeneous constraints, finite-ratio histories satisfy the required record, compactness, and connector hypotheses.
- In finite-dimensional normed spaces, hyperplane search with normals in a compact dual-sphere set is approximated by repeated homothetic cells.
- For locally rectifiable curves, admissible segments make the closure assumption automatic.
- For Shoreline search, the convex hull’s centered inradius exactly summarizes directional records and yields the cell’s online ratio functional.
- The log-polar illustration is not an angular-monotonicity assumption: cells may reverse angle, revisit angles, or have multiple radii at one angle.
8 From the continuum to finite polygonal cells
Polygonalization removes the remaining infinite-dimensional cell complexity. Exact evaluation, compact parameter bounds, and one-sided chord replacement reduce nearly optimal cells to finite, controlled polygonal optimization.
- The section combines an exact fixed-vertex evaluator, compact parameter bounds, and conservative polygonal approximation.
- The exact polygonal evaluator computes the ratio of a repeated polygonal cell from its edge phases and historical convex hull.
- For fixed edge count and bounded ratio, polygonal cells have compact parameter sublevels whose infimum is attained.
- Each short arc can be replaced by its chord while preserving a one-sided comparison that prevents artificial underestimation of online cost.
- The polygonal approximation controls the repeated cell’s ratio using a computable number of vertices.
9 Semialgebraic decision at fixed complexity
At fixed polygonal complexity, Shoreline-cell feasibility becomes a decidable first-order problem over the reals, enabling terminating rational-threshold tests and computable approximation of the optimum.
- Semialgebraic formulation: A polygonal cell with exactly N nonzero edges and ratio at most c is expressible by a first-order formula over the reals with rational coefficients.The variables include the scale factor, vertex coordinates, edge lengths, phase, and direction; the constraints are polynomial or finite disjunctions.
- Decision procedure: Quantifier elimination decides fixed-N feasibility, although the procedure is qualitative and expensive rather than numerically efficient.Its role is to guarantee termination for threshold decisions.
- Computable approximation: Theorem 10.1 provides a terminating algorithm that returns rational bounds of arbitrarily prescribed width for the optimal planar value.The construction combines effective cell bounds, polygonal reduction, threshold decidability, and rational bisection.
- Constructive output: A constructive quantifier-elimination procedure can also return an algebraic factor and polygonal cell whose ratio is at most C_2^* plus the requested approximation slack.The witness is algebraic because the feasibility problem is semialgebraic.
- Computational limitation: The resulting bounds are enormous, so the computability theorem does not provide a numerically competitive algorithm.The limitation comes from both covering constants and quantifier-elimination complexity.
11 Scope of the main chain
The paper separates the computability proof from a toolbox of exact identities that support memory reduction, dynamics, pruning, and spiral analysis without determining global optimality.
- Main chain: The main chain establishes self-similar reduction, effective bounds, polygonal replacement, and decidability, thereby proving C_2^* computable.These are presented as four distinct facts supporting the finite decision reduction.
- Toolbox scope: The toolbox is not used in the computability proof and instead supplies sliding memory, Bellman transitions, exclusion criteria, and relative-equilibrium analysis.Its results are intended for certified computation and spiral rigidity studies.
- Sliding memory: Exact sliding memory restricts useful history to a finite multiplicative window with logarithmic horizon log C.Earlier points are absorbed by the disk guaranteed at the current time.
- Bellman dynamics: The exact Bellman step updates position, hull, and directional support by contracting the old hull and taking a pointwise maximum with the new segment.This gives an autonomous normalized dynamics in logarithmic time.
- Spiral regime: Relative equilibria produce logarithmic spirals, but the stationary family’s value does not establish global optimality.The spiral reference value is approximately 13.81113517946.
- Geometric filters: The geometric filters are one-sided: violations certify impossibility, whereas satisfying all listed constraints does not certify historical realizability.This limits their use as exclusion tests rather than complete feasibility certificates.
13 Conclusion
The conclusion frames the paper’s main achievement as a finite, effective proof of computability while identifying practical certificate size and spiral optimality as unresolved challenges.
- Conclusion: The main chain converts an infinite history into a finite decision problem and proves computability of C_2^*.The separate toolbox contributes exact dynamics and structural diagnostics but is outside the proof chain.
- Open problems: The remaining challenge is to make certificates small enough for new numerical bounds and determine whether the spiral regime realizes the computable value.The paper does not resolve either practical certificate size or equality with the spiral reference.
B.1 Proof of homologous recutting
Homologous recutting preserves the relevant terminal support structure by exchanging a cell prefix for a scaled copy, while geometric predecessor constraints remain weaker than full historical viability.
- Support identity: The recut cell replaces the original support decomposition A_s∨B_s with B_s∨Q A_s.The two support maxima agree pointwise using the sign of A_s and positivity of the terminal inradius.
- Homologous recutting: The exact recutting argument preserves the terminal support and ratio under a new cell beginning at an admissible phase.A critical phase can serve as the cell’s new origin because the moved prefix is dilated by Q.
- Backward constraints: At the competitive threshold, predecessor hulls are constrained by geometric support inequalities derived from the future terminal hull.These constraints bound which old support can be inherited rather than refreshed by the new segment.
- Viability boundary: Every convex body satisfying the geometric predecessor interval reproduces the terminal hull geometrically, but full viability still requires an admissible history.Thus geometric reconstruction does not by itself establish historical realizability.
- Support budget: The support-budget decomposition combines multiplicative transport of stored support with nonnegative anisotropy dissipation.This identifies the two terms governing the cost of replacing a segment by a chord.
- Clock credit: A shorter viable block can receive clock credit when its terminal support loses at most ε/C in every direction.The saved length advances the clock by ε while lowering the future barrier by ε/C.
B.5.3 Renewal between completion times
The analysis models historical cost as discounted debt and develops geometric renewal and support arguments for self-similar search cells. It also derives a universal planar lower bound and uniqueness properties for the scale factor.
- Renewal dynamics: Historical cost is treated as debt that is discounted and replenished across phases.Pre-service can transfer this debt between phases but cannot remove it from the dynamics.
- Renewal dynamics: A logarithmic-spiral calculation relates radius and angle by eliminating the time parameter.The radius is proportional to t, while the angle is ω log t + θ_0.
- Geometric support: For κ>0 and τ∈(π,2π), the chord joining spiral points A and B supports the convex hull, with the origin’s perpendicular foot lying on the chord.The damped-sinusoid argument establishes global support by controlling all later maxima.
- Lower bound: Every finite-ratio planar strategy satisfies C≥1+π.The bound follows by comparing the normalized hull’s required disk and perimeter with the curve’s normalized length.
- Scale renewal: Recutting at a phase maximizing normalized length identifies a scale factor whose relevant function is strictly decreasing, yielding uniqueness of Q_1.The recutting argument uses projection variation and restores the original scale after analyzing the normalized regime.
C.2.2 Anisotropy cage
The anisotropy-cage analysis bounds support growth and renewal across phases, then derives local evolution equations for an active bottleneck face. Its geometric constraints are encoded by polynomial feasibility conditions.
- Cage bounds: A recut formula bounds normalized length at every phase when the recut ratio is below the spiral benchmark.Markov’s inequality applied to z−1 supplies an additional cap.
- Cage bounds: A hull containing a disk of radius M must connect opposite radial locations, while support-function Lipschitzness controls peak area.These geometric facts produce the second cap in the stated cage bounds.
- Support renewal: The current cell must renew terminal support because the preceding copy initially supplies (Q−1)h(θ), and support growth is limited by the velocity direction.The logarithmic budget tracks the ratio between historical and renewed support.
- Bottleneck dynamics: For an active bottleneck face, differentiating the two contacts gives Ω=(n⋅v)/ℓ and an inradius evolution equation involving the old branch’s curvature radius.The derivation equates normal velocities at the current and historical contacts.
- Semialgebraic encoding: The feasibility conditions use polynomial expressions, so FEAS_n(c) is a first-order real formula and the resulting disjunction is decidable.The encoding universally quantifies edge parameters and existentially quantifies a unit supporting normal.