Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
The Prefix Fréchet Similarity
verfasst von : Christian Scheffer
Erschienen in: WALCOM: Algorithms and Computation
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We present the prefix Fréchet similarity as a new measure for similarity of curves which is e.g. motivated by evacuation analysis and defined as follows. Given two (polygonal) curves T and \(T'\), we ask for two prefix curves of T and \(T'\) which have a Fréchet distance no larger than a given distance threshold \(\delta \ge 0\) w.r.t. \(L_1\) metric such that the sum of the prefix curves is maximal. As parameterized Fréchet measures as, e.g., the prefix Fréchet similarity are highly unstable w.r.t. to the value of the distance threshold \(\delta \), we give an algorithm that computes exactly the profile of the prefix Fréchet similarity, i.e., the complete functional relation between \(\delta \) and the prefix Fréchet similarity of T and \(T'\). This is the first efficient algorithm for computing exactly the whole profile of a parametrized Fréchet distance.
While the running time of our algorithm for computing the profile of the prefix Fréchet similarity is \(\mathcal {O}\left( n^3 \log n\right) \), we provide a lower bound of \(\varOmega (n^2)\) for the running time of each algorithm computing the profile of the prefix Fréchet similarity, where n denotes the number of segments on T and \(T'\). This implies that our running time is at most a near linear factor away from being optimal.