2026-07-19T20:50:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20003 2024-06-06T06:21:16Z ddc:004 open_access

Fréchet Edit Distance Fox, Emily Nayyeri, Amir Perry, Jonathan James Raichel, Benjamin Fréchet distance Edit distance Hardness We define and investigate the Fréchet edit distance problem. Given two polygonal curves π and σ and a threshhold value δ > 0, we seek the minimum number of edits to σ such that the Fréchet distance between the edited σ and π is at most δ. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emily Fox and Amir Nayyeri and Jonathan James Perry and Benjamin Raichel 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.58 urn:nbn:de:0030-drops-200032 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.58 eng https://creativecommons.org/licenses/by/4.0/legalcode