Similarity of polygonal curves in the presence of outliers (Q2444314): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 08:14, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Similarity of polygonal curves in the presence of outliers |
scientific article |
Statements
Similarity of polygonal curves in the presence of outliers (English)
0 references
9 April 2014
0 references
The authors discuss an alternative Fréchet distance measure that tolerates outliers. An exact solution for min-exclusion (MinEx) and max-inclusion (MaxIn) problems was presented by \textit{K. Buchin} et al. [in: Claire Mathieu (ed.), Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 645--654 (2009)], where the distances are measured using \(L_1\)-and \(L_\infty\)-metrics. Using Galois theory, the authors show that these problems are not solvable by radicals over \(Q\), when distances are measured using the \(L_2\)-metric and that the degree of the polynomial equations involved is unbounded in general. Algorithms that approximate solutions for the MinEx and MaxIn problems up to an additive approximation error \(\delta\) time the length of the input curves, are presented here.
0 references
Fréchet distance
0 references
similarity of polygonal curves
0 references
weighted shortest path
0 references
outliers
0 references
algorithm
0 references