2019/06/19 by Hugo A. Akitaya, Akitaya, Hugo A., Leonie Ryvkin +3
Computer Science · #Advanced Image and Video Retrieval Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1906.08141
openalex publication_date 2019/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The classical measure of similarity between two polygonal chains in Euclidean space is the Fréchet distance, which corresponds to the coordinated motion of two mobile agents along the chains while minimizing their maximum distance. As computing the Fréchet 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échet 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.