pith. sign in

arxiv: 1906.08141 · v1 · pith:YAM54Z5Pnew · submitted 2019-06-19 · 💻 cs.CG

Rock Climber Distance: Frogs versus Dogs

Hugo A. Akitaya , Leonie Ryvkin , Csaba D. T\'oth This is my paper

Pith reviewed 2026-05-25 19:55 UTC · model grok-4.3

classification 💻 cs.CG
keywords rock climber distancek-station distanceFréchet distanceHausdorff distancepolygonal chainsNP-hardnessapproximation algorithmcurve similarity
0
0 comments X

The pith

Alternating-move distances between polygonal chains match the Fréchet distance with unlimited moves but are NP-hard when limited to k moves.

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

The paper defines rock climber distance and k-station distance by letting two agents traverse polygonal chains with alternating moves instead of continuous simultaneous motion. When the number of moves is unlimited these new measures coincide with the Fréchet distance or the Hausdorff distance. When the number of moves is restricted to a parameter k, deciding whether the distance stays below a given threshold is NP-hard, yet a 2-approximation algorithm exists for the smallest such k. A reader would care because the alternating model offers a discrete alternative that preserves classical distances in the unrestricted case while exposing computational limits once moves are bounded.

Core claim

The rock climber distance and k-station distance are defined by requiring two agents to move alternately along their respective chains while keeping the maximum distance between them as small as possible. These distances are equivalent to the Fréchet distance or the Hausdorff distance when the number of moves is unlimited. When the number of moves is bounded by a given k, computing the distance is NP-hard, and there exists a 2-approximation algorithm that finds the minimum k for which the distance falls below a supplied threshold.

What carries the argument

The alternating-move model for two agents traversing polygonal chains, where one agent moves at a time while the maximum separation is minimized.

If this is right

  • Unlimited alternating moves produce exactly the same numerical distance as the classical Fréchet distance.
  • Unlimited alternating moves also produce the Hausdorff distance in some variants.
  • Deciding whether the distance is at most a given value is NP-hard once moves are restricted to k.
  • The smallest k achieving a distance threshold can be approximated within a factor of 2 in polynomial time.

Where Pith is reading between the lines

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

  • The NP-hardness result indicates that any exact algorithm for bounded k must be exponential in k or in the input size in the worst case.
  • The 2-approximation may be sufficient for applications that only need an order-of-magnitude estimate of the number of discrete steps required.
  • The equivalence proofs rely on constructing explicit alternating-move sequences that simulate continuous motion, suggesting the model is robust to small perturbations of the curves.

Load-bearing premise

The distance definitions rest on the agents moving alternately rather than continuously and simultaneously.

What would settle it

A pair of polygonal chains for which the minimum maximum separation under unlimited alternating moves differs from the Fréchet distance, or a polynomial-time algorithm that computes the exact minimum k for a given threshold.

Figures

Figures reproduced from arXiv: 1906.08141 by Csaba D. T\'oth, Hugo A. Akitaya, Leonie Ryvkin.

Figure 1
Figure 1. Figure 1: To project onto intervals a and a 0 we need to use the two straight line components above them, but then b has two preimages for its projection. polygonal domain with N vertices can be computed in O(N log N) time. Perhaps this method can be adapted to decide whether the rectilinear link distance between (0, 0) and (1, 1) in the free space Fε(P, Q) does not exceed a given parameter in time polynomial in k a… view at source ↗
Figure 2
Figure 2. Figure 2: Reduction from the instance (x1∨x3∨x5)∧(x1∨x5)∧(x2∨x3∨x4). The segments in the x-axis corresponding to the five variables are shown in green. (a) (b) (c) (d) p1 p2 p5 p3 p4 [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (a) Literal, (b) negation, (c) separation, and (d) clause gadgets. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Locally optimal solutions. (⇒) First, assume that A is a positive instance. For each variable xi assigned true, subdivide the subchains of P and Q that correspond to the literal gadgets of xi by placing blue (red) stations at the center of dashed (grey) circles as shown in [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An instance of the compatible axis-parallel segment cover problem. A solution of [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
read the original abstract

The classical measure of similarity between two polygonal chains in Euclidean space is the Fr\'echet distance, which corresponds to the coordinated motion of two mobile agents along the chains while minimizing their maximum distance. As computing the Fr\'echet distance takes near-quadratic time under the Strong Exponential Time Hypothesis (SETH), we explore two new distance measures, called rock climber distance and $k$-station distance, in which the agents move alternately in their coordinated motion that traverses the polygonal chains. We show that the new variants are equivalent to the Fr\'echet or the Hausdorff distance if the number of moves is unlimited. When the number of moves is limited to a given parameter $k$, we show that it is NP-hard to determine the distance between two curves. We also describe a 2-approximation algorithm to find the minimum $k$ for which the distance drops below a given threshold.

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

0 major / 2 minor

Summary. The paper introduces two new distance measures between polygonal chains, called rock climber distance and k-station distance. These are defined via alternating discrete moves by two agents (rather than continuous simultaneous motion), and the authors claim that the measures are equivalent to the Fréchet distance (or Hausdorff distance) when the number of moves is unbounded. For a fixed move budget k they prove NP-hardness of computing the distance, and they give a 2-approximation algorithm for the smallest k such that the distance falls below a given threshold.

Significance. If the equivalence, hardness, and approximation results hold, the work supplies discrete, alternating-move variants of Fréchet distance that recover the classical measures in the limit and come with explicit complexity and approximation guarantees. This is a meaningful addition to the computational-geometry literature on curve similarity, especially given the known conditional quadratic lower bound for Fréchet distance.

minor comments (2)
  1. The abstract states equivalence to Fréchet or Hausdorff depending on the variant; the manuscript should make explicit in the introduction which variant recovers which classical distance and under what precise conditions on the move set.
  2. The NP-hardness and 2-approximation statements are presented for a fixed k; the paper should clarify whether the hardness holds for the decision version (distance ≤ δ) or the optimization version, and whether the approximation is for the minimal k or for the distance value itself.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments appear in the provided report, so we have no specific points requiring point-by-point rebuttal or revision.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces rock climber distance and k-station distance as new measures defined via alternating discrete moves by two agents on polygonal chains. It then proves equivalence to Fréchet/Hausdorff distance under unbounded moves, NP-hardness for fixed k, and a 2-approximation for minimal k. These are standard algorithmic results resting on the explicit alternating-move model; no equations, fitted parameters, or self-citations appear in the provided text that reduce any claimed result to its own inputs by construction. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, invented entities, or non-standard axioms are identifiable from the given text. The results rely on standard computational geometry assumptions about polygonal chains in Euclidean space and standard complexity theory.

axioms (1)
  • domain assumption Polygonal chains are simple curves in Euclidean space with the usual distance metric.
    The distance definitions and equivalence statements presuppose standard Euclidean geometry on the input curves.

pith-pipeline@v0.9.0 · 5688 in / 1314 out tokens · 32546 ms · 2026-05-25T19:55:26.664764+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

34 extracted references · 34 canonical work pages · 1 internal anchor

  1. [1]

    Akitaya, Greg Aloupis, Jeff Erickson, and Csaba D

    Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba D. T´ oth. Recognizing weakly simple polygons. Discrete & Computational Geometry , 58(4):785–821, 2017. doi:10. 1007/s00454-017-9918-3

    work page 2017

  2. [2]

    The $k$-Fr\'echet distance

    Hugo A. Akitaya, Maike Buchin, Leonie Ryvkin, and J´ erˆ ome Urhausen. Thek-Fr´ echet distance. CoRR, abs/1903.02353, 2019. arXiv:1903.02353

    work page internal anchor Pith review Pith/arXiv arXiv 1903

  3. [3]

    Computing the Fr´ echet distance between two polyg- onal curves

    Helmut Alt and Michael Godau. Computing the Fr´ echet distance between two polyg- onal curves. Internat. J. Comput. Geom. Appl. , 5(1-2):75–91, 1995. doi:10.1142/ S0218195995000064

    work page 1995

  4. [4]

    Comparison of distance measures for planar curves

    Helmut Alt, Christian Knauer, and Carola Wenk. Comparison of distance measures for planar curves. Algorithmica, 38(1):45–58, 2004. doi:10.1007/s00453-003-1042-5

    work page doi:10.1007/s00453-003-1042-5 2004

  5. [5]

    Unique covering problems with geometric sets

    Pradeesha Ashok, Sudeshna Kolay, Neeldhara Misra, and Saket Saurabh. Unique covering problems with geometric sets. In Proc. 21st Computing and Combinatorics Conference (COCOON), volume 9198 of LNCS, pages 548–558, Cham, 2015. Springer. doi:10.1007/978-3-319-21398-9_43

    work page doi:10.1007/978-3-319-21398-9_43 2015

  6. [6]

    Local search strikes again: PTAS for variants of geometric covering and packing

    Pradeesha Ashok, Aniket Basu Roy, and Sathish Govindarajan. Local search strikes again: PTAS for variants of geometric covering and packing. In Proc. 23rd Comput- ing and Combinatorics Conference (COCOON) , volume 10392 of LNCS, pages 25–37, Cham, 2017. Springer. doi:10.1007/978-3-319-62389-4\_3

    work page doi:10.1007/978-3-319-62389-4 2017

  7. [7]

    Parameterized complexity of geometric covering problems having conflicts

    Aritra Banik, Fahad Panolan, Venkatesh Raman, Vibha Sahlot, and Saket Saurabh. Parameterized complexity of geometric covering problems having conflicts. In Proc. 15th Workshop on Algorithms and Data Structures (WADS) , volume 10389 of LNCS, pages 61–72, Cham, 2017. Springer. doi:10.1007/978-3-319-62127-2_6 . 16

    work page doi:10.1007/978-3-319-62127-2_6 2017

  8. [8]

    Line segment disk cover

    Manjanna Basappa. Line segment disk cover. In Proc. 4th Confference on Algorithms and Discrete Applied Mathematics (CALDAM) , volume 10743 of LNCS, pages 81–92, Cham, 2018. Springer. doi:10.1007/978-3-319-74180-2\_7

    work page doi:10.1007/978-3-319-74180-2 2018

  9. [9]

    Manjanna Basappa, Rashmisnata Acharyya, and Gautam K. Das. Unit disk cover problem in 2D. J. Discrete Algorithms , 33:193–201, 2015. doi:10.1016/j.jda.2015. 05.002

    work page doi:10.1016/j.jda.2015 2015

  10. [10]

    Ahmad Biniaz, Paul Liu, Anil Maheshwari, and Michiel H. M. Smid. Approximation algorithms for the unit disk cover problem in 2D and 3D. Comput. Geom., 60:8–18,

    work page

  11. [11]

    doi:10.1016/j.comgeo.2016.04.002

    work page doi:10.1016/j.comgeo.2016.04.002 2016

  12. [12]

    Why walking the dog takes time: Fr´ echet distance has no strongly subquadratic algorithms unless SETH fails

    Karl Bringmann. Why walking the dog takes time: Fr´ echet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. 55th IEEE Symposium on Foun- dations of Computer Science , pages 661–670, 2014. doi:10.1109/FOCS.2014.76

    work page doi:10.1109/focs.2014.76 2014

  13. [13]

    How difficult is it to walk the dog? In Abstracts of 23rd Europ

    Kevin Buchin, Maike Buchin, Christian Knauer, G¨ unther Rote, and Carola Wenk. How difficult is it to walk the dog? In Abstracts of 23rd Europ. Workshop on Comput. Geom. (EuroCG), pages 170–173, Graz, 2007

    work page 2007

  14. [14]

    Four Sovi- ets walk the dog: Improved bounds for computing the Fr´ echet distance

    Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer. Four Sovi- ets walk the dog: Improved bounds for computing the Fr´ echet distance. Discrete & Computational Geometry, 58(1):180–216, 2017. doi:10.1007/s00454-017-9878-7

    work page doi:10.1007/s00454-017-9878-7 2017

  15. [15]

    Exact algorithms for partial curve matching via the Fr´ echet distance

    Kevin Buchin, Maike Buchin, and Yusu Wang. Exact algorithms for partial curve matching via the Fr´ echet distance. InProc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 645–654, Philadelphia, 2009. SIAM. URL: http://dl.acm. org/citation.cfm?id=1496770.1496841

    work page arXiv 2009

  16. [16]

    SETH says: Weak Fr´ echet distance is faster, but only if it is continuous and in one dimension

    Kevin Buchin, Tim Ophelders, and Bettina Speckmann. SETH says: Weak Fr´ echet distance is faster, but only if it is continuous and in one dimension. In Proc. 30th ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2887–2901, 2019. doi: 10.1137/1.9781611975482.179

    work page doi:10.1137/1.9781611975482.179 2019

  17. [17]

    On the Computability of the Fr´ echet Distance Between Triangulated Sur- faces

    Maike Buchin. On the Computability of the Fr´ echet Distance Between Triangulated Sur- faces. PhD thesis, Free University, Berlin, 2007. URL: http://www.diss.fu-berlin. de/diss/receive/FUDISS_thesis_000000002618

    work page 2007

  18. [18]

    The k-Fr´ echet distance of polygonal curves

    Maike Buchin and Leonie Ryvkin. The k-Fr´ echet distance of polygonal curves. InAb- stracts of 34th Europ. Workshop on Computational Geometry (EuroCG) , Berlin, 2018. Article 43. URL: conference.imp.fu-berlin.de/eurocg18/

    work page 2018

  19. [19]

    Detecting weakly simple polygons

    Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In Proc. 26th ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1655–1670,

    work page

  20. [20]

    doi:10.1137/1.9781611973730.110. 17

    work page doi:10.1137/1.9781611973730.110

  21. [21]

    Phillips, and Ioannis Psarros

    Anne Driemel, Jeff M. Phillips, and Ioannis Psarros. The VC dimension of metric balls under Fr´ echet and Hausdorff distances. CoRR, abs/1903.03211, 2019. arXiv: 1903.03211

    work page arXiv 1903

  22. [22]

    Fowler, Mike Paterson, and Steven L

    Robert J. Fowler, Mike Paterson, and Steven L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. , 12(3):133–137, 1981. doi:10.1016/0020-0190(81)90111-3

    work page doi:10.1016/0020-0190(81)90111-3 1981

  23. [23]

    The within-strip discrete unit disk cover problem

    Robert Fraser and Alejandro L´ opez-Ortiz. The within-strip discrete unit disk cover problem. Theor. Comput. Sci. , 674:99–115, 2017. doi:10.1016/j.tcs.2017.01.030

    work page doi:10.1016/j.tcs.2017.01.030 2017

  24. [24]

    Goodman, J´ anos Pach, and Chee-K

    Jacob E. Goodman, J´ anos Pach, and Chee-K. Yap. Mountain climbing, ladder moving, and the ring-width of a polygon. Amer. Math. Monthly , 96(6):494–510, 1989

    work page 1989

  25. [25]

    Fr´ echet distance: How to walk your dog

    Sariel Har-Peled. Fr´ echet distance: How to walk your dog. InGeometric Approximation Algorithms, chapter 30. 2014. URL: https://sarielhp.org/book/

    work page 2014

  26. [26]

    The Fr´ echet distance revisited and extended

    Sariel Har-Peled and Benjamin Raichel. The Fr´ echet distance revisited and extended. ACM Trans. Algorithms, 10(1):3:1–3:22, 2014. doi:10.1145/2532646

    work page doi:10.1145/2532646 2014

  27. [27]

    The problem of compatible representatives

    Donald E Knuth and Arvind Raghunathan. The problem of compatible representatives. SIAM Journal on Discrete Mathematics , 5(3):422–427, 1992. doi:10.1137/0405033

    work page doi:10.1137/0405033 1992

  28. [28]

    Joseph S. B. Mitchell, Valentin Polishchuk, and Mikko Sysikaski. Minimum-link paths revisited. Comput. Geom., 47(6):651–667, 2014. doi:10.1016/j.comgeo.2013.12.005

    work page doi:10.1016/j.comgeo.2013.12.005 2014

  29. [29]

    Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski, and Haitao Wang. An op- timal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains. Algorithmica, 81(1):289–316, 2019. doi:10.1007/s00453-018-0446-1

    work page doi:10.1007/s00453-018-0446-1 2019

  30. [30]

    Mustafa and Saurabh Ray

    Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set prob- lems. Discrete & Computational Geometry , 44(4):883–895, 2010. doi:10.1007/ s00454-010-9285-9

    work page 2010

  31. [31]

    Packing and covering with non-piercing regions

    Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray. Packing and covering with non-piercing regions. Discrete & Computational Geometry, 60(2):471–492,

    work page

  32. [32]

    doi:10.1007/s00454-018-9983-2

    work page doi:10.1007/s00454-018-9983-2

  33. [33]

    More flexible curve matching via the partial Fr´ echet similarity

    Christian Scheffer. More flexible curve matching via the partial Fr´ echet similarity. Int. J. Comput. Geom. Appl. , 26:33–52, 2016. doi:10.1142/S0218195916500023

    work page doi:10.1142/s0218195916500023 2016

  34. [34]

    Veltkamp

    Ren´ e van Oostrum and Remco C. Veltkamp. Parametric search made practical.Comput. Geom., 28(2-3):75–88, 2004. doi:10.1016/j.comgeo.2004.03.006. 18

    work page doi:10.1016/j.comgeo.2004.03.006 2004