DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.58

Fréchet Edit Distance

Authors: Emily Fox, Amir Nayyeri, Jonathan James Perry, and Benjamin Raichel

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

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.

Cite as

Emily Fox, Amir Nayyeri, Jonathan James Perry, and Benjamin Raichel. Fréchet Edit Distance. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2024.58,
  author =	{Fox, Emily and Nayyeri, Amir and Perry, Jonathan James and Raichel, Benjamin},
  title =	{{Fr\'{e}chet Edit Distance}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{58:1--58:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.58},
  URN =		{urn:nbn:de:0030-drops-200032},
  doi =		{10.4230/LIPIcs.SoCG.2024.58},
  annote =	{Keywords: Fr\'{e}chet distance, Edit distance, Hardness}
}

Search Results

Documents authored by Perry, Jonathan James

Fréchet Edit Distance

Abstract

Cite as

Thanks for your feedback!

Could not send message