{"id":"3aa5a866-b167-4ead-a095-99f7f34d81e9","arxiv_id":"2608.12039","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For an agent starting anywhere in the plane, the optimal search-and-rescue strategy on the x-axis is either to go directly to the origin or to first visit a checkpoint at a closed-form distance, with the choice changing abruptly at about 15.6 degrees.","lead":"This paper solves a planar search-and-rescue problem exactly: an agent starting at any point must find an object on the x-axis and deliver it to the origin. The optimal strategy is characterized in closed form, including a sharp phase transition at a starting angle of about 15.6 degrees.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.2 never excludes a first hit on the negative x-axis; all cost formulas assume a positive checkpoint, so optimality of Algorithm 1 over all online algorithms is not proven.","rationale":"The reader's weakest assumption is essentially right: Theorem 2.2 is the load-bearing reduction, and its proof compresses arbitrary pre-origin motion into a positive checkpoint s without rigorously justifying that no other first-hit signed position or reversal pattern can beat the family A_s. I sharpen the concern to the signed first-hit issue because the displayed cost formulas use rho(theta,s) for a positive checkpoint; a negative first hit has a genuinely different distance, and for theta in (pi/2, pi) it is cheaper to reach. I do not have a counterexample: for cos(theta) < 0 the extra detour through the origin makes A_0 dominate any negative-checkpoint algorithm, and for cos(theta) > 0 the positive checkpoint dominates the negative one. The Section 3 algebra appears otherwise consistent, and the limits theta = 0 and theta = pi/2 recover known values, so the theorem is likely correct. The concern is that the paper as written does not prove the required reduction, and the Lemma 3.2 C-term typo shows the displayed algebra was not fully checked. Since this is a fixable proof gap rather than a demonstrated false claim, the conditional verdict is appropriate and no verdict change is needed.","tokens_in":13740,"tokens_out":34531,"duration_ms":340079,"concrete_test":"Independently re-derive Theorem 2.2 allowing the first x-axis hit to be any signed z in R. For the negative case z = -a, a > 0, write the competitive ratio of the algorithm B_a: move straight to (-a,0), then to O, then search [0,d] and return. Show analytically that for cos(theta) < 0 the first-leg-plus-origin term f(a) = sqrt(1 + 2a*cos(theta) + a^2) + a is minimized at a = 0 with value 1, so B_a is dominated by A_0; and for cos(theta) > 0, B_a is dominated by A_a because the positive checkpoint has a smaller first-leg cost and finds objects in (0,a] earlier. If either domination fails at some (theta,a), numerically compare B_a against min{CR(A_0,theta), CR(A_k_theta,theta)} over a grid of theta and a; a win for B_a would refute Theorem 1.1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The optimality theorem (Theorem 1.1 via Theorem 2.2) requires that restricting to the family A_s with s >= 0 loses nothing. The proof in Section 2.2 parametrizes the first x-axis contact only by its distance s and writes all costs using rho(theta,s) = sqrt(1 - 2s cos(theta) + s^2), which is the distance to the positive point (s,0). A strategy whose first contact is (-s,0) has first-leg cost sqrt(1 + 2s cos(theta) + s^2); for cos(theta) < 0 (theta > 90 degrees) this is strictly smaller, so the paper's cost formulas do not even bound such strategies from below. Claim 3's smax argument also assumes the pre-origin motion can be summarized as an interval [0,smax], but it never states or proves that the optimum over signed first hits lies on the nonnegative ray. Since Algorithm 1 only ever sends the agent to 0 or +r*k_|theta|, the whole optimality result rests on this unproved reduction. A secondary internal inconsistency supports the concern: Lemma 3.2's displayed constant C = alpha^2 - (2 + alpha*gamma)^2 is expanded as -(4 - alpha^2(1 - gamma^2)), dropping the -4*alpha*gamma term; the stated A,B,C do not yield the stated discriminant, though the final d- formula appears correct.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a planar search-and-rescue problem in which an agent starting at P_{\\theta,r}=(r\\cos\\theta,r\\sin\\theta) must find an object at an unknown distance on the positive x-axis and deliver it to the origin. The authors prove scale invariance, propose a one-parameter family A_s of algorithms that move directly to a checkpoint (s,0), then to the origin, then search outward, and derive closed-form competitive ratios for this family. They further show that the optimal checkpoint is either the origin or (r k_{|\\theta|},0), where k_{|\\theta|} is given explicitly, and they identify a critical angle \\theta^*\\approx 15.6^\\circ separating the two regimes. The main theorem (Theorem 1.1) asserts that Algorithm 1, built from this analysis, is optimal among all online algorithms, with the lower-bound half resting on the canonical-form reduction in Theorem 2.2.","tokens_in":13966,"tokens_out":14184,"duration_ms":142168,"significance":"If the result is fully established, it provides a complete optimal competitive analysis for a natural planar online search-and-delivery problem, including a phase transition determined by the starting angle. The paper has real strengths: the scale-invariance reduction is clean, the derivation of the competitive ratio for the family A_s is mostly self-contained, the limit \\theta=0 correctly recovers the known one-dimensional bound 1+\\sqrt{2}, and the claims are accompanied by numerical figures and a referenced Mathematica script. The phase-transition statement is sharp and falsifiable. However, the proof of Theorem 2.2 contains a gap that is load-bearing for the optimality claim, and the proof of Lemma 3.2 contains an algebraic error in displayed coefficients. Both issues are local in nature, and the underlying results appear plausible, but the manuscript in its current form does not yet establish optimality over all online algorithms.","major_comments":[{"comment":"The proof never excludes a first contact with the negative x-axis. All cost formulas in the paper use \\rho(\\theta,s)=\\sqrt{1-2s\\cos\\theta+s^2}, the distance from P_\\theta to the positive point (s,0), and the explored region is described as the interval [0,s_{\\max}]. A strategy whose first x-axis contact is at (-s,0) has first-leg cost \\sqrt{1+2s\\cos\\theta+s^2}, which for \\cos\\theta<0 is strictly smaller than the positive-point formula, and the explored interval before reaching the origin would be [s_{\\max},0] or a signed interval, not [0,s_{\\max}]. Since Theorem 2.2 is the lower-bound half of Theorem 1.1, the optimality claim is not proven over all online algorithms until a lemma rules out negative checkpoints or the analysis is extended to signed s.","section":"Section 2.2, Theorem 2.2"},{"comment":"The displayed coefficients A, B, C are inconsistent. From C=\\alpha^2-(2+\\alpha\\gamma)^2 one obtains -4-4\\alpha\\gamma+\\alpha^2(1-\\gamma^2), not -(4-\\alpha^2(1-\\gamma^2)); the -4\\alpha\\gamma term is dropped. With the stated A, B, and C, the stated discriminant \\Delta=16\\alpha^2(1-\\gamma^2)(1+\\alpha\\gamma) does not follow. The final formula for d_- is correct if one uses the standard polynomial with C'=(2+\\alpha\\gamma)^2-\\alpha^2 and A'=(\\alpha+2\\gamma)^2-\\alpha^2, but as written the proof of Lemma 3.2, which supplies the critical point used throughout Section 3, is invalid.","section":"Section 3.1, Lemma 3.2"},{"comment":"The derivation of the closed-form \\theta^* depends on a degree-11 factorization, shown in Equation (12), and on rejecting three of its factors as spurious. The text delegates the elimination and the substitution checks to a CAS call in an accompanying Mathematica script without giving the eliminated polynomial or the detailed verification of each factor against the unsquared equation. Because the exact form of \\theta^* is a central advertised contribution, the reader cannot verify from the manuscript alone that the factorization is correct and that no genuine root is discarded. The paper should either include the eliminated polynomial and the spurious-root checks, or make the script's verification steps part of the proof.","section":"Section 3.3, Theorem 3.9"}],"minor_comments":[{"comment":"The reduction assumes \\theta\\in[0,\\pi) by reflection about the x-axis, but the abstract and Algorithm 1 state the result for -\\pi\\le\\theta\\le\\pi. It should be stated explicitly that all formulas are even in \\theta and that reflection maps the negative-angle case to the positive-angle case.","section":"Section 2.1"},{"comment":"In the case \\gamma>0, the proof says that d_+ > (2+\\alpha\\gamma)/(\\alpha+2\\gamma) > d_- can be verified from the explicit formulas, but the verification is not shown. This inequality is needed to reject d_+ as spurious and should be stated with a short derivation or moved to an appendix.","section":"Section 3.1, Lemma 3.2"},{"comment":"The claim that CR(s,s,\\theta) is unimodal is justified by a derivative calculation, but the derivative is given in compressed form; writing the algebra for \\partial/\\partial s \\,[1+2s/(\\rho+s)] would make the monotonicity argument easier to check.","section":"Section 3.2, Theorem 3.8"},{"comment":"The statement that CR(A_0,\\theta) is decreasing in \\theta is correct pointwise, but the proof phrase \"since \\rho(\\theta,d) is increasing in \\theta for each fixed d>0\" should also note that this pointwise monotonicity is preserved by the supremum over d; a one-sentence justification would remove ambiguity.","section":"Section 3.3, Theorem 3.9"},{"comment":"In the pseudocode, k_{|\\theta|} is defined only through a displayed formula; for readability, the formula should be labeled or repeated inside the algorithm box, since the reader must otherwise cross-reference Equation (9).","section":"Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The central risk is the signed-checkpoint gap in Theorem 2.2. If the authors can prove that an optimal algorithm never benefits from a first contact on the negative x-axis, or can extend the analysis to signed checkpoints, the main theorem would likely stand. The algebraic error in Lemma 3.2 appears to be a typo, since the final d_- formula is correct, but it must be fixed in the revision. I would also recommend independent verification of the factorization in Equation (12) rather than relying only on the referenced script."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper does something real: it takes the one-dimensional search-and-rescue problem, moves the start to an arbitrary point in the plane, and produces exact competitive ratios, a closed-form checkpoint k_|θ|, and a phase transition at θ* ≈ 15.6°. The θ=0 limit recovers the known 1+√2 line result, the figures match the formulas, and the algebra in Lemmas 3.1–3.7 is careful. The reduction to min{A0, A_kθ} via monotonicity is clever, and the CAS-supported closed form for θ* is a genuine contribution. I believe the result, not just the paper, is new.\n\nThe soft spots are real but, I think, repairable. Theorem 2.2, the canonical-form lower bound, is under-specified in exactly the place the stress-test flags: it parametrizes the first x-axis hit by distance s without signing it, and for θ > π/2 a first hit on the negative axis has a smaller first-leg cost than ρ(θ,s) assumes. This is not fatal—going to any negative point before the origin is dominated by going straight to the origin, so the A0 conclusion for those angles survives—but the proof needs to say that explicitly. The smax argument also compresses arbitrary pre-origin motion into an s → smax → O path; the cost that path incurs is indeed the cheapest way to explore [0,smax] and end at O, but the proof never says why reversals or interleaved searches cannot do better. The gap is in the exposition, not the math, but Theorem 2.2 is load-bearing, so a referee should push on it.\n\nTwo smaller things. Lemma 3.2's displayed constant C is missing a -4αγ term; the discriminant and subsequent d− formula use the correct C, so it is a typo, but a confusing one. And the θ* derivation relies on a CAS factorization and spurious-root rejection that are checked by substitution but not fully machine-certified; the linked script helps, but the paper should spell out the sign checks more.\n\nWho is this for? Search theorists and competitive-analysis people who want a clean benchmark or an extension exercise. It is specialized, and the idealized model limits practical reach, but within the subfield it is a solid, citable result. I would bring it to a reading group and I would cite it if I worked on geometric search. It deserves a serious referee: my verdict would be conditional, not reject. Send it to review, with the request that the authors fix the negative-axis case in Theorem 2.2, tighten the smax argument, and correct the C typo.","headline":"A clean, mostly self-contained closed-form solution to a natural planar search-and-rescue variant; the optimality theorem has a fixable gap around negative-axis first hits, but the result looks right.","tokens_in":14566,"tokens_out":6217,"would_cite":true,"duration_ms":68236,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","90B40"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every starting point in the plane, one of two routes is optimal for search-and-rescue, with the switch at about 15.6 degrees.","keywords":["search and rescue","competitive ratio","online algorithm","geometric search","checkpoint","phase transition","mobile agent","x-axis search"],"falsifier":"Take a specific angle inside the cone, say $\\theta=10^\\circ$, and simulate the non-canonical strategy that enters the x-axis at some $s$, sweeps partway back toward the origin, then returns to the origin and searches outward; if any choice of $s$ and sweep length gives a worst-case ratio smaller than the paper's value $CR(A_{k_\\theta},\\theta)$ from equations (9) and (11), the canonical-form theorem and the claimed optimality fail.","tokens_in":13439,"feed_emoji":"🧭","tokens_out":12452,"duration_ms":117426,"temperature":0.7,"pith_summary":"This paper establishes the optimal online strategy for a search-and-rescue agent that starts anywhere in the plane, must find an object at an unknown distance along the positive x-axis, and must carry it to the origin. The optimal strategy is always one of two shapes: either go straight to the origin and then search outward, or first land on a specific checkpoint on the x-axis computed from the starting angle, then return to the origin, then search. The paper derives closed-form competitive ratios for both shapes and shows that the better one depends only on the angle of the starting point, not on its distance from the origin. The crossover happens at a critical angle $\\theta^* \\approx 15.6^\\circ$, so an agent starting within that forward cone should use a nonzero checkpoint while an agent starting outside the cone should head straight for the origin. If correct, this reduces a continuous search-and-delivery planning problem to a simple two-option decision rule with an explicit formula.","feed_headline":"A 15.6-degree cone decides the optimal rescue route","feed_subtitle":"If starting inside the cone, land at a computed checkpoint first; outside it, head straight for the origin.","key_machinery":"The central object is the one-parameter family of algorithms $A_s$, indexed by the checkpoint distance $s$ on the x-axis, with $\\rho(\\theta,s)=\\sqrt{1-2s\\cos\\theta+s^2}$ as the distance from the starting point to the checkpoint. The argument turns on two identities: the root $k_\\theta=\\frac{5+2\\cos\\theta+\\cos 2\\theta+\\sqrt{2\\cos^2\\theta\\,(11+4\\cos\\theta+\\cos 2\\theta)}}{8}$ where the two candidate worst cases $CR_{d\\le s}(s,\\theta)$ and $CR(s,s,\\theta)$ cross, and the angle equation $4\\cos^3\\theta+8\\cos^2\\theta-11=0$ whose unique root in $(0,\\pi/2)$ is the critical angle. The derivative analysis of the ratio curve $CR(s,d,\\theta)$ identifies $d_-(s,\\theta)$ as the unique worst-case object distance and proves it is decreasing in $s$, which forces the global minimum of $CR(A_s,\\theta)$ to lie at one of the two endpoints $s=0$ or $s=k_\\theta$.","core_discovery":"After rescaling the starting radius $r$ away, the paper proves that every optimal algorithm can be put in the canonical form $A_s$: fly directly to a point $(s,0)$ on the x-axis, walk back to the origin, then search away from the origin along the positive x-axis until the object is found and deliver it. For this family the worst-case competitive ratio is the maximum of two closed-form expressions, one for objects found before reaching the origin and one for objects found later; a derivative analysis locates the worst object distance $d_-(s,\\theta)$ and shows the ratio is minimized only at $s=0$ or at $s=k_\\theta$, where $k_\\theta$ is an explicit function of $\\cos\\theta$. Comparing the two candidates gives the phase transition: the checkpoint at $(r\\cdot k_{|\\theta|},0)$ is optimal for $|\\theta|<\\theta^*$, and the origin is optimal for $|\\theta|\\ge\\theta^*$, with $\\theta^* = \\arccos\\!\\big(\\tfrac{1}{12}\\big(-8 + \\sqrt[3]{1864-312\\sqrt{33}} + 2\\sqrt[3]{233+39\\sqrt{33}}\\big)\\big) \\approx 0.2716$ rad $\\approx 15.6^\\circ$. The resulting competitive ratio is independent of $r$ and recovers the one-dimensional bound $1+\\sqrt{2}$ at $\\theta=0$.","pith_inferences":["The paper's machinery implies a testable extension the authors do not state: if the search is confined to a bounded interval rather than the full ray, the same ratio curve should acquire a third boundary case, and the optimal checkpoint would become a function of the interval length.","I infer from the structure that a two-agent version would split the outward sweep at the checkpoint, and the $15.6^\\circ$ threshold computed here would serve as the baseline for deciding whether splitting is ever worthwhile.","Another unstated consequence: because the formulas are continuous in $\\theta$ except at the phase boundary, the competitive-ratio landscape has a sharp but non-smooth kink at $\\theta^*$, which could make the threshold visible in simulated trial data before any theoretical derivation."],"forward_implications":["At $\\theta=0$ the optimal checkpoint is $((2+\\sqrt{2})/2)\\,r$ and the competitive ratio is $1+\\sqrt{2}\\approx 2.414$, recovering the one-dimensional search-and-rescue bound.","For every starting angle with $|\\theta|\\ge\\theta^*$, the direct-to-origin strategy is optimal; its ratio decreases from $5/4$ at $\\theta=\\pi/2$ to $1$ as $\\theta$ approaches $\\pi$.","For every starting angle with $|\\theta|<\\theta^*$, the optimal strategy places the first checkpoint at $(r\\,k_{|\\theta|},0)$ on the x-axis before any search begins.","Since the ratio is independent of $r$, the same angular decision rule applies at every distance: the checkpoint distance simply scales linearly with the starting distance.","No online algorithm can beat $\\min\\{CR(A_0,\\theta), CR(A_{k_\\theta},\\theta)\\}$ for any starting point, so the two-option rule is exactly optimal."],"supporting_citations":[{"why":"Defines the one-dimensional search-and-rescue problem whose optimal checkpoint $(2+\\sqrt{2})/2$ and competitive ratio $1+\\sqrt{2}$ the planar solution must recover at $\\theta=0$; the planar variant is presented as an extension of this framework, and the boundary case anchors Theorem 3.9.","marker":"[10]"}],"fun_headline_variants":["Phase transition at 15.6° sets optimal rescue path","Rescue route: land at checkpoint only inside 15.6° cone","Optimal search: head to origin unless start angle under 15.6°","15.6° threshold dictates whether to detour or go straight","Checkpoint landing is optimal only for narrow cone of start angles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The optimality result hinges on the assumption that an optimal agent goes straight to a checkpoint on the x-axis, returns to the origin, and then searches outward monotonically; the paper compresses any early zigzagging into a first-hit point and a farthest point, but does not directly analyze pre-origin paths that reverse direction or search before reaching the origin.","fun_headline_variants_meta":{"raw":{"variants":["Phase transition at 15.6° sets optimal rescue path","Rescue route: land at checkpoint only inside 15.6° cone","Optimal search: head to origin unless start angle under 15.6°","15.6° threshold dictates whether to detour or go straight","Checkpoint landing is optimal only for narrow cone of start angles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000196,"raw_usage":{"total_tokens":1419,"prompt_tokens":1065,"completion_tokens":354,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":681,"completion_tokens_details":{"reasoning_tokens":260}},"tokens_in":681,"tokens_out":354,"duration_ms":3408,"temperature":1.0,"reasoning_tokens":260,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:19:59.850229+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a specific angle inside the cone, say $\\theta=10^\\circ$, and simulate the non-canonical strategy that enters the x-axis at some $s$, sweeps partway back toward the origin, then returns to the origin and searches outward; if any choice of $s$ and sweep length gives a worst-case ratio smaller than the paper's value $CR(A_{k_\\theta},\\theta)$ from equations (9) and (11), the canonical-form theorem and the claimed optimality fail.","supporting_citations":[{"cited_title":"In: Rajsbaum, S., Balliu, A., Daymude, J.J., Olivetti, D","cited_arxiv_id":null,"evidence_quote":"Defines the one-dimensional search-and-rescue problem whose optimal checkpoint $(2+\\sqrt{2})/2$ and competitive ratio $1+\\sqrt{2}$ the planar solution must recover at $\\theta=0$; the planar variant is presented as an extension of this framework, and the boundary case anchors Theorem 3.9."}],"review_version":1}