Similarity of Polygonal Curves in the Presence of Outliers

Date Added: Dec 2012
Format: PDF

The Frechet distance is a well studied and commonly used measure to capture the similarity of polygonal curves. Unfortunately, it exhibits a high sensitivity to the presence of outliers. Since the presence of outliers is a frequently occurring phenomenon in practice, a robust variant of Frechet distance is required which absorbs outliers. The authors explain such a variant here. In this modified variant, their objective is to minimize the length of sub curves of two polygonal curves that need to be ignored (MinEx problem), or alternately, maximize the length of sub curves that are preserved (MaxIn problem), to achieve a given Frechet distance. An exact solution to one problem would imply an exact solution to the other problem.