2015/06/16 by Omrit Filtser, Filtser, Omrit, Matthew J. Katz +1
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1506.04861
openalex publication_date 2015/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce the discrete Fréchet gap and its variants as an alternative measure of similarity between polygonal curves. We believe that for some applications the new measure (and its variants) may better reflect our intuitive notion of similarity than the discrete Fréchet distance (and its variants), since the latter measure is indifferent to (matched) pairs of points that are relatively close to each other. Referring to the frogs analogy by which the discrete Fréchet distance is often described, the discrete Fréchet gap is the minimum difference between the longest and shortest positions of the leash needed for the frogs to traverse their point sequences. We present an optimization scheme, which is suitable for any monotone function defined for pairs of distances such as the gap and ratio functions. We apply this scheme to two variants of the discrete Fréchet gap, namely, the one-sided discrete Fréchet gap with shortcuts and the weak discrete Fréchet gap, to obtain O(n2 log2 n)-time algorithms for computing them.