Fréchet edit distance

Joint work with Amir Nayyeri, Jonathan James Perry, Benjamin Raichel

Proceedings of the 40th International Symposium on Computational Geometry (SoCG), 58:1–58:15, 2024

Abstract

In this paper we define and investigate the Fréchet edit distance problem. Here, 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 curve 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.