DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2024.37

Approximating the Fréchet Distance When Only One Curve Is c-Packed

Authors: Joachim Gudmundsson, Tiancheng Mai, and Sampson Wong

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract

One approach to studying the Fréchet distance is to consider curves that satisfy realistic assumptions. By now, the most popular realistic assumption for curves is c-packedness. Existing algorithms for computing the Fréchet distance between c-packed curves require both curves to be c-packed. In this paper, we only require one of the two curves to be c-packed. Our result is a nearly-linear time algorithm that (1+ε)-approximates the Fréchet distance between a c-packed curve and a general curve in ℝ^d, for constant values of ε, d and c.

Cite as

Joachim Gudmundsson, Tiancheng Mai, and Sampson Wong. Approximating the Fréchet Distance When Only One Curve Is c-Packed. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2024.37,
  author =	{Gudmundsson, Joachim and Mai, Tiancheng and Wong, Sampson},
  title =	{{Approximating the Fr\'{e}chet Distance When Only One Curve Is c-Packed}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.37},
  URN =		{urn:nbn:de:0030-drops-221649},
  doi =		{10.4230/LIPIcs.ISAAC.2024.37},
  annote =	{Keywords: Fr\'{e}chet distance, c-packed curve, approximation algorithm}
}

Search Results

Documents authored by Mai, Tiancheng

Approximating the Fréchet Distance When Only One Curve Is c-Packed

Abstract

Cite as

Thanks for your feedback!

Could not send message