{"id":"88c270f0-03fc-4a24-b3d7-d12c79da8a27","arxiv_id":"2606.01147","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Introduces Fréchet TSP for two coordinated curves, with a near-linear algorithm for the discrete case and NP-hardness for the continuous case.","lead":"The paper introduces a variant of the traveling salesman problem in which two curves visit a shared set of points while minimizing their Fréchet distance. A smart generalist might read it to understand new algorithmic tools for coordinated multi-agent routing in geometry.","discovery_kind":"new_application","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's assessment that only the abstract was available is accurate, and the strongest claim rests on standard definitions that the abstract invokes without apparent contradiction. No load-bearing technical concern can be substantiated without the missing manuscript details.","tokens_in":1660,"tokens_out":248,"duration_ms":17720,"concrete_test":"Extract the claimed running time and the reduction for the continuous case from the full manuscript; re-derive the time bound from the algorithm description and check whether the hardness reduction produces instances whose continuous Fréchet distance correctly encodes the NP-hard problem.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim asserts a near-linear algorithm under discrete Fréchet distance together with NP-hardness under continuous Fréchet distance for the two-curve TSP variant on a finite point set. The provided abstract states the result directly and invokes the standard definitions of the two distances; no internal inconsistency, hidden assumption about point-set dimension, or circularity in the claimed complexity separation is visible from the given material. Because the full manuscript text referenced in the prompt is not supplied here, no concrete technical flaw in the argument can be located.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper introduces a variant of the TSP in which two curves are constructed from a shared finite point set such that their Fréchet distance is minimized. It claims a near-linear-time algorithm for the discrete Fréchet distance, examines several optimization variants (curve-length minimization and balanced site assignment), and proves NP-hardness under the continuous Fréchet distance.","tokens_in":1762,"tokens_out":226,"duration_ms":13942,"significance":"If the claimed near-linear algorithm and the hardness separation are correct, the work would establish a useful complexity distinction between discrete and continuous Fréchet distances in a coordinated-routing setting and could inform practical applications in network planning.","major_comments":[{"comment":"Abstract: the central claims assert the existence of a near-linear algorithm under discrete Fréchet distance and an NP-hardness proof under continuous Fréchet distance, but the provided text supplies no derivation, pseudocode, reduction, or proof sketch, preventing verification of the soundness of either result.","section":null}],"minor_comments":[],"recommendation":"uncertain","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their review. The major comment concerns the level of detail in the abstract; we address it below and note that the full manuscript contains the algorithm and proof.","responses":[{"response":"The abstract is a high-level summary of contributions, as is standard. The near-linear algorithm for discrete Fréchet distance (including its approach, correctness argument, and time analysis) appears in full in the body of the paper, and the NP-hardness reduction for the continuous case is likewise detailed with the construction and proof. If the submission format made the body text unavailable to the referee, that is an issue we will correct. To aid verification from the abstract alone, we will add one or two sentences sketching the main algorithmic idea and the reduction source in the revised abstract.","revision_made":"partial","referee_comment":"[—] Abstract: the central claims assert the existence of a near-linear algorithm under discrete Fréchet distance and an NP-hardness proof under continuous Fréchet distance, but the provided text supplies no derivation, pseudocode, reduction, or proof sketch, preventing verification of the soundness of either result."}],"tokens_in":1195,"tokens_out":257,"duration_ms":19648,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is a new TSP variant for two curves that must cover a point set while minimizing their Fréchet distance. The authors claim a near-linear algorithm under discrete Fréchet and NP-hardness under continuous Fréchet.\n\nThis extends the usual role of Fréchet distance from measuring similarity to enforcing closeness in a joint traversal. The motivation for two agents staying close during routing is straightforward.\n\nThe paper handles the core problem and adds variants for length minimization and load balancing between agents. The discrete-continuous split is handled separately, which aligns with how these distances behave in algorithms.\n\nA soft spot is that the abstract alone gives no evidence for the complexity claims. The near-linear time and the hardness proof need to be checked in the body. If the full paper delivers clean proofs without hidden assumptions on the point set or dimension, the results hold up.\n\nThis is aimed at researchers in computational geometry who work on distance measures or TSP in geometric settings. Someone looking for new primitives in coordinated motion planning would find it relevant.\n\nThe work shows clear thinking on the problem definition and the choice of distance variants. I would send it to peer review.","headline":"This paper defines a two-curve TSP variant that minimizes Fréchet distance between the paths and claims a near-linear algorithm for the discrete case plus NP-hardness for the continuous case.","tokens_in":2232,"tokens_out":321,"would_cite":false,"duration_ms":21763,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Two curves from one point set minimize discrete Fréchet distance in near-linear time, but the continuous version is NP-hard.","keywords":["Fréchet distance","Traveling salesman problem","discrete Fréchet distance","continuous Fréchet distance","NP-hardness","near-linear algorithm","computational geometry"],"falsifier":"A concrete finite point set on which the near-linear discrete algorithm returns curves whose discrete Fréchet distance exceeds the true minimum, or a polynomial-time algorithm for any instance of the continuous version.","tokens_in":2578,"feed_emoji":"🗺️","tokens_out":612,"duration_ms":27285,"temperature":0.7,"pith_summary":"The paper defines a TSP variant in which two curves are built from the same finite point set so that the Fréchet distance between the curves is as small as possible. This models two agents that must visit sites while remaining close throughout their traversals. A near-linear algorithm solves the problem when the discrete Fréchet distance is used. The continuous Fréchet distance version is shown to be NP-hard. The authors also handle variants that minimize total curve length or balance the number of sites assigned to each curve.","feed_headline":"Near-linear algorithm for discrete Fréchet TSP variant","feed_subtitle":"Two curves from one point set minimize discrete Fréchet distance in near-linear time; continuous case is NP-hard.","key_machinery":"The discrete Fréchet distance on finite point sets, which permits a near-linear algorithm to pair vertices on the two curves without requiring continuous traversal along edges.","core_discovery":"We introduce the problem of constructing two curves whose vertices come from a given point set while keeping their Fréchet distance small. We present a near-linear algorithm for this problem under the discrete Fréchet distance, explore variants including length minimization and balanced site assignment, and prove that the problem is NP-hard under the continuous Fréchet distance.","pith_inferences":["The two-curve model may extend to three or more agents required to stay mutually close.","It connects to multi-robot coordination where proximity constraints must hold along entire paths.","Approximation algorithms could still be developed for the continuous case despite its hardness.","The hardness result suggests that continuous models are often replaced by discrete ones in practice."],"forward_implications":["The discrete version yields practical computation for routing and network planning tasks on large point sets.","Length-minimizing and site-balancing variants remain tractable under the discrete distance.","The continuous version requires approximation methods or heuristics because it is NP-hard."],"fun_headline_variants":["Discrete Fréchet two-curve TSP in near-linear time","Two point-set curves minimize discrete Fréchet distance","Continuous Fréchet TSP variant proven NP-hard","Near-linear discrete Fréchet TSP from shared points","Fréchet-constrained two-curve TSP near-linear for discrete"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The standard definitions of discrete and continuous Fréchet distance on finite point sets suffice for an efficient algorithm in the discrete case and a hardness proof in the continuous case.","fun_headline_variants_meta":{"raw":{"variants":["Discrete Fréchet two-curve TSP in near-linear time","Two point-set curves minimize discrete Fréchet distance","Continuous Fréchet TSP variant proven NP-hard","Near-linear discrete Fréchet TSP from shared points","Fréchet-constrained two-curve TSP near-linear for discrete"]},"model":"grok-4.3","cost_usd":0.005749,"raw_usage":{"total_tokens":2639,"prompt_tokens":625,"num_sources_used":0,"completion_tokens":78,"cost_in_usd_ticks":57490500,"prompt_tokens_details":{"text_tokens":625,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1936,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":625,"tokens_out":78,"duration_ms":14622,"temperature":1.0,"reasoning_tokens":1936,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-28T16:03:09.569940+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete finite point set on which the near-linear discrete algorithm returns curves whose discrete Fréchet distance exceeds the true minimum, or a polynomial-time algorithm for any instance of the continuous version.","supporting_citations":[],"review_version":1}