pith. sign in

arxiv: 2606.01147 · v1 · pith:WE4XHDRSnew · submitted 2026-05-31 · 💻 cs.CG

On Fr\'echet Traveling Salesmen Problems

Omrit Filtser , Tzalik Maimon , Michal Moiseev This is my paper

Pith reviewed 2026-06-28 16:03 UTC · model grok-4.3

classification 💻 cs.CG
keywords Fréchet distanceTraveling salesman problemdiscrete Fréchet distancecontinuous Fréchet distanceNP-hardnessnear-linear algorithmcomputational geometry
0
0 comments X

The pith

Two curves from one point set minimize discrete Fréchet distance in near-linear time, but the continuous version is NP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

Core claim

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.

What carries the argument

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.

If this is right

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

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

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

Load-bearing premise

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.

What would settle it

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.

read the original abstract

The Fr\'echet distance is a well-studied distance measure between two curves. In this work, we demonstrate that the merit of Fr\'echet distance extends beyond evaluating similarity, and introduce a new setting in which it proves useful. Consider a situation where two agents are required to visit a given set of sites, while staying close to each other throughout their traversal. In this paper, we study problems where the goal is to construct two curves whose vertices are from a given set of points, under the constraint that the Fr\'echet distance between the curves is kept as small as possible. This problem can be viewed as a variant of the Traveling Salesman Problem (TSP), and thus may be of interest in routing, network planning and more. We present a near-linear algorithm for this problem under the discrete Fr\'echet distance, and explore several variants of the problem, including minimizing the lengths of the curves and balancing the number of sites assigned to each agent. Lastly, we prove that the problem is NP-hard under the continuous Fr\'echet Distance.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

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.

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 (1)
  1. 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.

Simulated Author's Rebuttal

1 responses · 0 unresolved

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.

read point-by-point responses

  1. Referee: [—] 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.

    Authors: 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: partial

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The provided abstract states algorithmic and hardness results directly from standard definitions of discrete and continuous Fréchet distance on point sets, with no equations, reductions, self-citations, or derivations shown. No load-bearing step reduces to a fitted input, self-definition, or author-specific uniqueness theorem. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract only; no free parameters, axioms, or invented entities are described.

pith-pipeline@v0.9.1-grok · 5718 in / 991 out tokens · 33574 ms · 2026-06-28T16:03:09.569940+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

59 extracted references · 16 canonical work pages · 2 internal anchors

  1. [1]

    Scott , title =

    Piotr Berman and Marek Karpinski and Alex D. Scott , title =. Electron. Colloquium Comput. Complex. , volume =. 2003 , url =. TR03-049 , timestamp =

    2003

  2. [2]

    Jaywalking Your Dog: Computing the Fr

    Anne Driemel and Sariel Har. Jaywalking Your Dog: Computing the Fr. 2013 , url =. doi:10.1137/120865112 , timestamp =

    work page doi:10.1137/120865112 2013

  3. [3]

    Anil Maheshwari and J. Fr. Comput. Geom. , volume =. 2011 , url =. doi:10.1016/J.COMGEO.2010.09.008 , timestamp =

    work page doi:10.1016/j.comgeo.2010.09.008 2011

  4. [4]

    Kevin Buchin and Maike Buchin and Wouter Meulemans and Bettina Speckmann , title =. Comput. Geom. , volume =. 2019 , url =. doi:10.1016/J.COMGEO.2018.09.002 , timestamp =

    work page doi:10.1016/j.comgeo.2018.09.002 2019

  5. [5]

    Alon Efrat and Quanfu Fan and Suresh Venkatasubramanian , title =. J. Math. Imaging Vis. , volume =. 2007 , url =. doi:10.1007/S10851-006-0647-0 , timestamp =

    work page doi:10.1007/s10851-006-0647-0 2007

  6. [6]

    Journal of the ACM (JACM) , volume=

    Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems , author=. Journal of the ACM (JACM) , volume=. 1998 , publisher=

    1998

  7. [7]

    Constant Approximation of Fr

    Siu. Constant Approximation of Fr. Proceedings of the 57th Annual

  8. [8]

    Maike Buchin and Bernhard Kilgus , title =. Comput. Geom. , volume =. 2022 , url =. doi:10.1016/J.COMGEO.2021.101842 , timestamp =

    work page doi:10.1016/j.comgeo.2021.101842 2022

  9. [9]

    Har-Peled, Sariel and Raichel, Benjamin , journal=. The Fr. 2014 , publisher=

    2014

  10. [10]

    Geodesic Fr

    Iv, Atlas F Cook and Wenk, Carola , journal=. Geodesic Fr. 2010 , publisher=

    2010

  11. [11]

    Canadian Conference on Computational Geometry , year=

    Approximate Matching of Curves to Point Sets , author=. Canadian Conference on Computational Geometry , year=

  12. [12]

    International Conference on Combinatorial Optimization and Applications , pages=

    Discretely following a curve , author=. International Conference on Combinatorial Optimization and Applications , pages=. 2013 , organization=

    2013

  13. [13]

    Hardness Results on Curve/Point Set Matching with Fr\'echet Distance

    Paul Accisano and Alper. Hardness Results on Curve/Point Set Matching with Fr. CoRR , volume =. 2012 , url =. 1211.2030 , timestamp =

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  14. [14]

    , author=

    Staying Close to a Curve. , author=. CCCG , year=

  15. [15]

    A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram in a Simple Polygon

    A nearly optimal algorithm for the geodesic voronoi diagram in a simple polygon , author=. arXiv preprint arXiv:1803.03526 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  16. [16]

    Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon , url =

    Ahmad Biniaz and Prosenjit Bose and Anil Maheshwari and Michiel Smid , doi =. Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon , url =. Computational Geometry , keywords =. 2016 , bdsk-url-1 =

    2016

  17. [17]

    Theoretical Computer Science , volume=

    The directed Hausdorff distance between imprecise point sets , author=. Theoretical Computer Science , volume=. 2011 , publisher=

    2011

  18. [18]

    Hopcroft, John E and Karp, Richard M , journal=. An n\^. 1973 , publisher=

    1973

  19. [19]

    Proceedings of the National Academy of Sciences , volume=

    Two theorems in graph theory , author=. Proceedings of the National Academy of Sciences , volume=. 1957 , publisher=

    1957

  20. [20]

    Approximating the Fr

    Driemel, Anne and Har-Peled, Sariel and Wenk, Carola , booktitle=. Approximating the Fr

  21. [21]

    Clustering time series under the Fr

    Driemel, Anne and Krivo. Clustering time series under the Fr. Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms , pages=. 2016 , organization=

    2016

  22. [22]

    arXiv preprint arXiv:2404.18738 , year=

    A faster algorithm for the Fr 'echet distance in 1D for the imbalanced case , author=. arXiv preprint arXiv:2404.18738 , year=

    work page arXiv

  23. [23]

    Tight bounds for approximate near neighbor searching for time series under the Fr

    Bringmann, Karl and Driemel, Anne and Nusser, Andr. Tight bounds for approximate near neighbor searching for time series under the Fr. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

    2022

  24. [24]

    Computing the Fr

    Buchin, Kevin and L. Computing the Fr. Computational Geometry , volume=. 2023 , publisher=

    2023

  25. [25]

    arXiv preprint arXiv:2203.04548 , year=

    On Flipping the Fr ' \ e \ chet distance , author=. arXiv preprint arXiv:2203.04548 , year=

    work page arXiv

  26. [26]

    Computing the Fr

    Alt, Helmut and Godau, Michael , journal=. Computing the Fr. 1995 , publisher=

    1995

  27. [27]

    SETH says: Weak Fr

    Buchin, Kevin and Ophelders, Tim and Speckmann, Bettina , booktitle=. SETH says: Weak Fr. 2019 , organization=

    2019

  28. [28]

    Sur quelques points du calcul fonctionnel , journal =

    Fr. Sur quelques points du calcul fonctionnel , journal =

  29. [29]

    2019 , publisher=

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , author=. 2019 , publisher=

    2019

  30. [30]

    2014 IEEE 55th Annual Symposium on Foundations of Computer Science , pages=

    Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails , author=. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science , pages=. 2014 , organization=

    2014

  31. [31]

    The multiple traveling salesman problem: an overview of formulations and solution procedures , journal =

    Tolga Bektas , keywords =. The multiple traveling salesman problem: an overview of formulations and solution procedures , journal =. 2006 , issn =. doi:https://doi.org/10.1016/j.omega.2004.10.004 , url =

    work page doi:10.1016/j.omega.2004.10.004 2006

  32. [32]

    A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy , journal =

    Omar Cheikhrouhou and Ines Khoufi , keywords =. A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy , journal =. 2021 , issn =. doi:https://doi.org/10.1016/j.cosrev.2021.100369 , url =

    work page doi:10.1016/j.cosrev.2021.100369 2021

  33. [33]

    arXiv preprint arXiv:2109.07524 , year=

    Exact and approximation algorithms for many-to-many point matching in the plane , author=. arXiv preprint arXiv:2109.07524 , year=

    work page arXiv

  34. [34]

    Proceedings of the seventh annual symposium on Computational geometry , pages=

    Transitions in geometric minimum spanning trees , author=. Proceedings of the seventh annual symposium on Computational geometry , pages=

  35. [35]

    Graphs and combinatorics , volume=

    Efficient many-to-many point matching in one dimension , author=. Graphs and combinatorics , volume=. 2007 , publisher=

    2007

  36. [36]

    Discrete & Computational Geometry , volume=

    Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications , author=. Discrete & Computational Geometry , volume=. 2020 , publisher=

    2020

  37. [37]

    Proceedings of the twentieth annual ACM symposium on theory of computing , pages=

    Geometry helps in matching , author=. Proceedings of the twentieth annual ACM symposium on theory of computing , pages=

  38. [38]

    IEEE Transactions on Computers , volume=

    Fast algorithms for constructing minimal spanning trees in coordinate spaces , author=. IEEE Transactions on Computers , volume=. 1978 , publisher=

    1978

  39. [39]

    Journal of Algorithms , volume=

    Linear time algorithms for knapsack problems with bounded weights , author=. Journal of Algorithms , volume=. 1999 , publisher=

    1999

  40. [40]

    Proceedings of the sixth annual symposium on Computational geometry , pages=

    Euclidean minimum spanning trees and bichromatic closest pairs , author=. Proceedings of the sixth annual symposium on Computational geometry , pages=

  41. [41]

    1987 , publisher=

    Algorithms in combinatorial geometry , author=. 1987 , publisher=

    1987

  42. [42]

    Discrete & Computational Geometry , volume=

    An O (n log n) algorithm for the all-nearest-neighbors problem , author=. Discrete & Computational Geometry , volume=. 1989 , publisher=

    1989

  43. [43]

    Discrete & Computational Geometry , volume=

    On nearest-neighbor graphs , author=. Discrete & Computational Geometry , volume=. 1997 , publisher=

    1997

  44. [44]

    Mitchell, Joseph S. B. , title =. SIAM Journal on Computing , volume =. 1999 , doi =. https://doi.org/10.1137/S0097539796309764 , abstract =

    work page doi:10.1137/s0097539796309764 1999

  45. [45]

    Approximately matching polygonal curves with respect to the Fr

    Mosig, Axel and Clausen, Michael , journal=. Approximately matching polygonal curves with respect to the Fr. 2005 , publisher=

    2005

  46. [46]

    Computing discrete Fr

    Eiter, Thomas and Mannila, Heikki and others , year=. Computing discrete Fr

  47. [47]

    Simplifying 3D Polygonal Chains Under the Discrete Fr \'e chet Distance

    Bereg, Sergey and Jiang, Minghui and Wang, Wencheng and Yang, Boting and Zhu, Binhai. Simplifying 3D Polygonal Chains Under the Discrete Fr \'e chet Distance. LATIN 2008: Theoretical Informatics. 2008

    2008

  48. [48]

    A PTAS for the Min-Max Euclidean Multiple TSP , doi =

    Mount, David and Monroe, Mary , year =. A PTAS for the Min-Max Euclidean Multiple TSP , doi =

  49. [49]

    arXiv preprint arXiv:2506.14713 , year=

    Linear Planar 3-SAT and Its Applications in Planning , author=. arXiv preprint arXiv:2506.14713 , year=

    work page arXiv

  50. [50]

    Journal of Algorithms , volume=

    Approximation algorithms for TSP with neighborhoods in the plane , author=. Journal of Algorithms , volume=. 2003 , publisher=

    2003

  51. [51]

    ACM Trans

    Shalita, Alon and Zwick, Uri , title =. ACM Trans. Algorithms , month = apr, articleno =. 2010 , issue_date =. doi:10.1145/1721837.1721850 , abstract =

    work page doi:10.1145/1721837.1721850 2010

  52. [52]

    Theoretical Computer Science , volume=

    On min--max r-gatherings , author=. Theoretical Computer Science , volume=. 2011 , publisher=

    2011

  53. [53]

    Revue fran

    The vehicle routing problem , author=. Revue fran. 1976 , publisher=

    1976

  54. [54]

    Papadimitriou , abstract =

    Christos H. Papadimitriou , abstract =. The Euclidean travelling salesman problem is NP-complete , journal =. 1977 , issn =. doi:https://doi.org/10.1016/0304-3975(77)90012-3 , url =

    work page doi:10.1016/0304-3975(77)90012-3 1977

  55. [55]

    Journal of Computer and System Sciences , volume=

    New inapproximability bounds for TSP , author=. Journal of Computer and System Sciences , volume=. 2015 , publisher=

    2015

  56. [56]

    1978 , publisher=

    Grundzuge der mengenlehre , author=. 1978 , publisher=

    1978

  57. [57]

    Kisfaludi-Bak, S. A gap-. Journal of the ACM , volume=. 2025 , publisher=

    2025

  58. [58]

    ACM Transactions on Algorithms (TALG) , volume=

    Fine-grained complexity analysis of two classic TSP variants , author=. ACM Transactions on Algorithms (TALG) , volume=. 2020 , publisher=

    2020

  59. [59]

    Journal of the ACM (JACM) , volume=

    Net and prune: A linear time algorithm for euclidean distance problems , author=. Journal of the ACM (JACM) , volume=. 2015 , publisher=

    2015