Fréchet Edit Distance

Abstract

We define and investigate the Fréchet edit distance problem. Given two polygonal curves $\pi$ and $\sigma$ and a threshhold value $\delta >0$, we seek the minimum number of edits to $\sigma$ such that the Fréchet distance between the edited $\sigma$ and $\pi$ is at most $\delta$. For the edit operations we consider three cases, namely, deletion of vertices, insertion of vertices, or both. For this basic problem we consider a number of variants. Specifically, we provide polynomial time algorithms for both discrete and continuous Fréchet edit distance variants, as well as hardness results for weak Fréchet edit distance variants.

To appear in SoCG 2024