{"id":"867ec991-feca-4545-92f8-a134ab92157a","arxiv_id":"2411.15391","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"New upper bounds and Pareto curves for average-case disk-perimeter inspection, plus a complete worst-case solution for inspecting any arc, improving on Isbell (1957) and correcting Gluss (1961).","lead":"This paper studies how one or more agents starting at the center of a circular obstacle can inspect every point on its perimeter, visible only from outside the disk. It gives new worst-case-optimal routes for partial arcs, improves the best known average-case inspection time for a single agent from about 3.63 to 3.55, and provides trade-off curves between worst-case and average-case performance.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised (1+1/k)-approximation guarantee for the NLP method is not proved: Lemma 4 is only a one-way lift, so the claimed systematic convergence to the true optimum is unsupported.","rationale":"The reader's weakest-assumption analysis identifies exactly the gap I consider most load-bearing. The central mathematical claim that this paper introduces a systematic method with a guaranteed (1+1/k)-approximation to the continuous optimum is not supported by the provided lemmas. Lemma 4 supplies a valid upper-bound construction, but it does not establish that the discrete optimum is close to the continuous optimum. Without a converse or an explicit rounding argument for non-touching optima, the NLP outputs in Theorem 3 and Theorem 4 cannot be interpreted as provably near-optimal; they are only feasible upper bounds. This does not invalidate the feasibility of the reported trajectories, so the headline average-case upper bounds may still be correct. However, the paper's advertised methodological contribution and the implied convergence of the discretization are not proved. The appropriate disposition remains conditional: the feasible-construction claims can be accepted with the numerical data verified, while the stronger approximation guarantee should be either proved or explicitly downgraded to a conjecture.","tokens_in":14,"tokens_out":21245,"duration_ms":319405,"concrete_test":"Prove or disprove the missing converse: for an arbitrary feasible, non-touching continuous trajectory C for Ap(8,theta,c), let A_i be the first point of C on tangent line L_i, and form the PolySegment A_0 -> A_1 -> ... -> A_k. Show that this PolySegment is feasible to Ap(k,theta,c) and that its discrete average cost s_d satisfies s_d <= (1+1/k) times the continuous optimum, or exhibit a no-touch trajectory for which this fails. A numerical probe to accompany the analytical check: run NLP-avg(k,c,epsilon) with k=1000,2000,4000 using the provably optimal trajectory from [39] and compare (1+1/k)D_k with the proven optimum 3.549259; if the ratio exceeds 1+1/k or fails to shrink like 1/k, the claimed guarantee does not follow from the stated assumptions.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2.3.2 claims that the discretization-plus-NLP approach is \"guaranteed to be within 1+1/k of the true optimum\" under the assumption that the global optimizer induces a trajectory not touching the disk. Lemma 4, however, proves only one direction: any feasible discrete PolySegment trajectory lifts to a continuous feasible trajectory whose average cost is at most (1+1/k) times the discrete cost. This is an upper-bound construction and does not bound the gap between the discrete NLP optimum and the continuous optimum. To certify the claimed guarantee, one needs the converse: the discrete optimum over PolySegment trajectories must be within a (1+1/k) factor of the continuous optimum, typically by rounding an optimal non-touching continuous trajectory to a PolySegment with vertices on the tangent lines L_i. The no-touch assumption is stated but never used in a proof; no lemma shows that non-touching optima can be well approximated by PolySegment trajectories. Therefore the systematic convergence claim, which is a central advertised contribution, is not established. The individual upper bounds in Table 1 remain valid as feasible constructions, but the paper's stronger methodological claim that the NLP solutions converge to the true optimum lacks support.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies n unit-speed agents that start at the center of a unit disk and must inspect every point of the disk perimeter, where a perimeter point is covered only if an agent outside the disk has unobstructed visibility of it. It proves a worst-case optimal bound for the partial inspection problem P(c) (Theorem 1), derives the n-agent worst-case bound as a corollary (Theorem 2), proposes average-case upper bounds for S_n using the Extended-PolySegment (EPS) trajectory family and nonlinear programming (Theorem 3), and gives Pareto upper bounds for the trade-off between worst-case and average-case inspection cost (Theorem 4). The paper also identifies numerical errors in Gluss's 1961 heuristic evaluations and provides corrected values.","tokens_in":30203,"tokens_out":12284,"duration_ms":111143,"significance":"If the results stand, the paper makes three useful contributions: it extends Isbell's worst-case shoreline result to partial arcs and thereby gives a unified proof of known multi-agent worst-case bounds; it improves on Gluss's corrected average-case heuristics, including a clean analytic bound for n≥3 agents; and it introduces a tractable parametric family (EPS) for exploring worst-/average-case trade-offs. The correction of Gluss's numerical errors is careful and valuable. The main caveats are that the headline numerical upper bounds for n=1,2 are computer-assisted without accompanying code or data, and the claimed systematic (1+1/k)-approximation guarantee for the discretization-plus-NLP method is not actually proved. These issues are fixable, but they currently affect the strength of the advertised methodology.","major_comments":[{"comment":"The claim that the NLP solution is \"guaranteed to be within 1+1/k of the true optimum\" is not supported by the results proved in the paper. Lemma 4 shows only one direction: any feasible discrete PolySegment trajectory lifts to a feasible continuous trajectory whose average cost is at most (1+1/k) times the discrete cost. This gives an upper bound on the continuous optimum in terms of a particular discrete feasible trajectory, but it does not bound the gap between the discrete NLP optimum and the continuous optimum. The reverse direction, in which a non-touching continuous optimal trajectory is rounded to a PolySegment with vertices on the tangent lines L_i, is never proved, and the stated \"no-touch\" assumption is not used in any lemma. The individual upper bounds in Theorem 3 remain valid as feasible constructions, but the systematic-convergence claim in Section 2.3.2 should either be proved or explicitly restated as a heuristic with one-sided certificates.","section":"Section 2.3.2 and Lemma 4"},{"comment":"The numerical upper bounds for n=1,2 and the Pareto curve are not reproducible from the manuscript. The proof of Theorem 8 reports solutions of (NLP-avg(k,c,epsilon)) obtained with Ipopt for k=1000 and k=2000, but no code, data files, or explicit optimizer vectors (theta,t_1,...,t_k) are provided; the figures showing the t_i values cannot be used to certify the quoted numbers. Since the values 3.5509015 and 1.7946051 are central to the claimed improvement over Gluss's corrected bounds, the authors should provide the feasible trajectories as high-precision data or as runnable code. The same concern applies to Theorem 4, whose statement refers to a figure rather than to an explicit table or data set supporting the Pareto upper bounds.","section":"Section 4.2, Theorem 3, and Theorem 4"},{"comment":"The displayed derivative f1'(theta)=(sin(theta)-sin(theta))/cos(theta) is identically zero, so the monotonicity analysis in Lemma 7 is invalid as printed. The correct derivative appears to be (sin(theta)-sin(c))/cos^2(theta); with this correction the case analysis can be repaired, but the proof of Theorem 1 needs to be updated accordingly. In addition, the proof of Theorem 1 invokes Isbell's convexity theorem as a black box; since that theorem is the main geometric input for the partial-arc extension, the authors should state explicitly that it is an external result and explain how it carries over to the partial-arc setting.","section":"Appendix A.1, Lemma 7"}],"minor_comments":[{"comment":"The Discussion invokes reference [39] as \"subsequent work\" that validates the approach and gives a true optimum of 3.549259. This reference is an arXiv preprint by one of the authors, so it is not independent confirmation; the provenance and status of the result should be stated clearly.","section":"Section 6"},{"comment":"The asymptotic statement that the average cost converges to 1 + pi^2/(6 n^2) + o(1/n^3) is asserted without derivation; a short expansion or an explicit reference would make the claim easier to verify.","section":"Section 2.2 and Theorem 3"},{"comment":"Several figure captions and axis labels appear corrupted in the full text (e.g., strings like \"i255/3/7/8/9\"), which makes the figures difficult to read. These should be regenerated or relabeled.","section":"Figures 10 and 15"}],"recommendation":"major_revision","confidential_remarks":"The paper contains a valuable worst-case extension and a clean analytic average-case upper bound for n>=3, and the correction of Gluss's numerical errors is a genuine service to the literature. My main concern is that the methodological claim of a (1+1/k)-approximation guarantee is overclaimed relative to the proved one-way lift. With a careful rewording or a proof of the reverse direction, and with the numerical artifacts made available, the paper would be suitable for publication. I do not recommend rejection, because the feasible-construction upper bounds and the worst-case theorems can stand independently of the unsupported convergence claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper is worth reading but needs a stronger spine before I'd trust the headline. The core result—a complete worst-case solution to the partial inspection problem P(c) for every arc length c—is a genuine extension of Isbell, and it gives a clean alternative proof of the known n-agent worst-case bounds. That part is likely correct and is the paper's real contribution. The average-case work is also a step forward: the authors catch a numerical error in Gluss, correct his evaluation from 3.4795 to 3.64529, and produce upper bounds that beat the corrected heuristics. The Pareto trade-off curve is a reasonable extra, though it is presented mostly as a figure.\n\nThe soft spots are where the paper oversells itself. The claimed (1+1/k) approximation guarantee for the discretization-plus-NLP method is not proved. Lemma 4 is a one-way lift: a feasible discrete trajectory lifts to a continuous one with cost at most (1+1/k) times the discrete cost. That gives an upper bound on continuous cost, but it says nothing about the gap between the discrete NLP optimum and the true continuous optimum. To make the systematic convergence claim you need the converse rounding direction, and it's absent. The no-touch assumption is stated but never used in a proof. So the individual upper bounds in Table 1 are valid as feasible constructions, but the advertised guarantee that the NLP solutions approach the true optimum is unsupported. This matters because the paper leans on that guarantee to justify why we should prefer this method over ad-hoc heuristics.\n\nThe numerical work also lacks reproducibility. No code, no data, no script are shipped; the reported numbers come from Ipopt local optima. That is acceptable for upper-bound constructions, but it means any reader who wants to verify the table has to redo the NLP from scratch. Theorem 4 is essentially a figure, and a numeric Pareto table would have been cheap to include. The appendix has a derivative typo, but that is minor.\n\nOne more thing: the Discussion leans on the same author's subsequent paper [39] as independent confirmation of optimality. That is not independent, and it should be labeled as later work by the same group, not cited as an external proof.\n\nThe worst-case theorem and the corrected Gluss numbers are solid enough to justify a serious referee. The paper deserves peer review, but it should come back with major revisions: prove or explicitly retract the approximation guarantee, release code and data for the NLP results, and give a numeric Pareto table. Who should read it? Search-theory and mobile-agent people will want the worst-case formula and the corrected bounds; the methodological claim should be ignored until fixed.","headline":"Real progress on a classic problem, but the flagship methodological claim outruns the proof; the worst-case theorem and corrected numerical work stand on their own.","tokens_in":30741,"tokens_out":1658,"would_cite":true,"duration_ms":17893,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B40","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The authors prove new upper bounds for the average time to inspect a unit disk's perimeter with n mobile agents, beating 1961 heuristics and giving the first Pareto trade-off curve.","keywords":["disk inspection","shoreline problem","mobile agents","average-case analysis","worst-case analysis","Pareto upper bounds","nonlinear programming","search theory"],"falsifier":"Solve the continuous single-agent average-case problem independently, for instance with the Fermat-principle/ODE reduction cited in the paper's discussion, and check whether the optimal trajectory touches the disk anywhere. If it does, the discretization guarantee collapses; if it does not, the guarantee holds and the reported bound should converge to the true optimum (about 3.549259) as $k$ grows.","tokens_in":29739,"feed_emoji":"🎯","tokens_out":8693,"duration_ms":73894,"temperature":0.7,"pith_summary":"The paper studies n unit-speed agents that start at the center of a unit disk and must inspect the entire perimeter, where a point is considered seen only when an agent is outside the disk with unobstructed line of sight. For the worst case, it solves the partial-inspection problem of covering an arc of length c, which yields, as a corollary, a single proof of the optimal worst-case times for any number of agents. For the average case, it introduces a systematic method: discretize the perimeter, solve a nonlinear program for a polygonal trajectory whose vertices lie on tangent lines, then translate the discrete solution back to a feasible continuous trajectory with at most a $(1+1/k)$ cost blow-up. This improves the 1961 average-case heuristics of Gluss (which the paper shows contained numerical errors) to $3.5509015$ for one agent, $1.7946051$ for two agents, and $\\frac{n}{2\\pi}\\log\\frac{1+\\sin(\\pi/n)}{1-\\sin(\\pi/n)}$ for $n\\ge 3$, with the average asymptotically approaching $1+\\frac{\\pi^2}{6n^2}$. The same machinery produces Pareto upper bounds for trading worst-case against average-case performance in the single-agent problem.","feed_headline":"New averages beat 1961 disk-inspection heuristics","feed_subtitle":"Discretization plus nonlinear programming give the first improvement in 60+ years and a Pareto trade-off curve.","key_machinery":"The central object is the ExtendedPolySegment (EPS) trajectory: the agent first moves from the disk center to a deployment point $A_0=(1,\\tan\\theta)$ and then travels a polygonal chain whose $k$ vertices $A_i$ lie on the tangent lines $L_i$ to the disk at the sampled perimeter points. The load-bearing identity is the lift in Lemma 4, which shows that when the tangent parameters satisfy $t_i \\ge \\frac{1-\\cos((c-2\\theta)/k)}{\\sin((c-2\\theta)/k)}$, each segment $A_{i-1}\\to A_i$ inspects all perimeter points between the two tangent contacts, so the discrete trajectory is feasible for the continuous problem and its average cost is at most $(1+1/k)$ times the discrete average. This lift converts numerical NLP solutions into provable continuous upper bounds, and the same family of trajectories, optimized with objective $\\lambda\\cdot\\text{worst}+(1-\\lambda)\\cdot\\text{average}$, gives the Pareto trade-off curve.","core_discovery":"The paper's central discovery is that the continuous disk-inspection problem can be attacked through a discrete auxiliary problem with a rigorous one-way lift: any feasible discrete inspection trajectory built as a polygonal chain with vertices on the tangent lines at sampled perimeter points is also feasible for the continuous problem, and its average cost is at most $(1+1/k)$ times the discrete average. Optimizing such chains with a nonlinear program yields explicit trajectories that beat all previously reported average-case upper bounds, and the family is flexible enough that, when the objective is a weighted sum of worst-case and average-case cost, it supplies the first Pareto frontier for the single-agent problem. The paper also proves the optimal worst-case cost for inspecting any arc of length $c$, which simultaneously recovers, by partitioning the perimeter equally among agents, the known optimal worst-case results for $n=2,3,4,\\dots$ agents.","pith_inferences":["If the no-touch assumption can be proved (as the follow-up work cited by the authors suggests), the same NLP pipeline becomes a certified approximation scheme for the disk problem and might extend to any convex obstacle whose visibility is defined by tangent half-planes.","The gap between the paper's best single-agent bound ($3.5509015$) and the subsequently proved optimum ($3.549259$) is about $0.0016$, so a natural test is whether increasing $k$ in the same pipeline closes the gap completely.","Because the lift in Lemma 4 is one-way (discrete to continuous), the same discretization technique could be adapted to other search and evacuation problems where worst- and average-case guarantees are both of interest."],"forward_implications":["For $n\\ge 3$ agents, the new average inspection time is $\\frac{n}{2\\pi}\\log\\frac{1+\\sin(\\pi/n)}{1-\\sin(\\pi/n)}$, which asymptotically behaves as $1+\\frac{\\pi^2}{6n^2}$, so a large team can inspect the perimeter in essentially the minimum time needed to reach the boundary.","The worst-case partial-inspection theorem covers every arc length $c$, so the paper's Corollary 2 subsumes the known optimal worst-case results for $n=2,3,4,\\dots$ agents in a single proof.","The single-agent Pareto curve gives a family of operating points between the worst-case-optimal trajectory (cost $\\approx 6.397$) and the average-case-optimal trajectory (length $\\approx 6.867$), so a designer can choose how much worst-case guarantee to sacrifice for better average performance.","The paper's correction of Gluss's numerical evaluations means that the previously accepted 'best' average-case bounds from 1961 were too optimistic; the new construction is the first genuine improvement.","Under the no-touch assumption, the discretization-plus-NLP methodology yields upper bounds that are within $1+1/k$ of the continuous optimum, so increasing $k$ gives a systematic way to approach the true optimum."],"supporting_citations":[{"why":"Supplies the optimal worst-case single-agent trajectory that the paper generalizes via the partial-inspection problem.","marker":"[48]"},{"why":"Provides the 1961 average-case heuristics and the numbers the paper corrects and strictly improves.","marker":"[46]"},{"why":"Gives worst-case optimal bounds for shoreline search with n≥4 agents, which the paper recovers as a corollary.","marker":"[1]"},{"why":"Gives worst-case optimal bounds for n=2,3 agents, also recovered by the paper's partial-inspection theorem.","marker":"[30]"},{"why":"Ipopt interior-point solver used to obtain the numerical NLP solutions for the EPS trajectories.","marker":"[23]"},{"why":"JuMP modeling language used to formulate and solve the nonlinear programs underlying the upper bounds.","marker":"[31]"},{"why":"Cited follow-up work proving that the same methodology yields the true optimum of the average-case problem, supporting the paper's conjectured effectiveness.","marker":"[39]"}],"fun_headline_variants":["Disk inspection averages improved for first time since 1961","Pareto frontier for worst-case vs average disk inspection","NLP discretization beats 1961 disk-inspection upper bounds","Worst and average disk inspection jointly optimized via NLP","New trajectories improve disk inspection averages and Pareto"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The systematic approximation guarantee rests on the assumption that the true optimal inspection trajectory never touches the disk; if that fails, the claim that the discrete solution is within $1+1/k$ of the continuous optimum is unproved, though each constructed trajectory still gives a valid upper bound.","fun_headline_variants_meta":{"raw":{"variants":["Disk inspection averages improved for first time since 1961","Pareto frontier for worst-case vs average disk inspection","NLP discretization beats 1961 disk-inspection upper bounds","Worst and average disk inspection jointly optimized via NLP","New trajectories improve disk inspection averages and Pareto"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000186,"raw_usage":{"total_tokens":1343,"prompt_tokens":981,"completion_tokens":362,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":597,"completion_tokens_details":{"reasoning_tokens":283}},"tokens_in":597,"tokens_out":362,"duration_ms":4232,"temperature":1.0,"reasoning_tokens":283,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:23:11.804530+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve the continuous single-agent average-case problem independently, for instance with the Fermat-principle/ODE reduction cited in the paper's discussion, and check whether the optimal trajectory touches the disk anywhere. If it does, the discretization guarantee collapses; if it does not, the guarantee holds and the reported bound should converge to the true optimum (about 3.549259) as $k$ grows.","supporting_citations":[{"cited_title":"Acharjee, K","cited_arxiv_id":null,"evidence_quote":"Gives worst-case optimal bounds for shoreline search with n≥4 agents, which the paper recovers as a corollary."},{"cited_title":"Dobrev, R","cited_arxiv_id":null,"evidence_quote":"Gives worst-case optimal bounds for n=2,3 agents, also recovered by the paper's partial-inspection theorem."},{"cited_title":"Ipopt: Interior point optimizer.https://github.com/coin-or/Ipopt","cited_arxiv_id":null,"evidence_quote":"Ipopt interior-point solver used to obtain the numerical NLP solutions for the EPS trajectories."},{"cited_title":"Dunning, J","cited_arxiv_id":null,"evidence_quote":"JuMP modeling language used to formulate and solve the nonlinear programs underlying the upper bounds."},{"cited_title":"Optimal average disk-inspection via Fermat’s Principle.arXiv preprint arXiv:2509.06334, 2025","cited_arxiv_id":null,"evidence_quote":"Cited follow-up work proving that the same methodology yields the true optimum of the average-case problem, supporting the paper's conjectured effectiveness."}],"review_version":1}