Similarity of polygonal curves in the presence of outliers (Q2444314)

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.