1995/03/01 by Helmut Alt, HELMUT ALT, MICHAEL GODAU +1 · 1,037 citations
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Data mining #Digital Image Processing Techniques #Function (biology) #Geometry #Mathematics #Measure (data warehouse) #Polygonal chain
paper · doi:10.1142/s0218195995000064
published in International Journal of Computational Geometry & Applications 05(01n02), 75-91 (World Scientific)
crossref issued 1995/03/01 · crossref published 1995/03/01 · crossref published-print 1995/03/01 · openalex publication_date 1995/03/01 · crossref created 2004/11/10 · crossref published-online 2011/11/20 · crossref deposited 2019/08/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06 · crossref indexed 2026/08/06
As a measure for the resemblance of curves in arbitrary dimensions we consider the so-called Fréchet-distance, which is compatible with parametrizations of the curves. For polygonal chains P and Q consisting of p and q edges an algorithm of runtime O(pq log(pq)) measuring the Fréchet-distance between P and Q is developed. Then some important variants are considered, namely the Fréchet-distance for closed curves, the nonmonotone Fréchet-distance and a distance function derived from the Fréchet-distance measuring whether P resembles some part of the curve Q.