License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.26
URN: urn:nbn:de:0030-drops-60485
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6048/
Go to the corresponding LIPIcs Volume Portal

Maheshwari, Anil ; Sack, Jörg-Rüdiger ; Scheffer, Christian

Approximating the Integral Fréchet Distance

pdf-format:
LIPIcs-SWAT-2016-26.pdf (0.7 MB)

Abstract

We present a pseudo-polynomial time (1 + epsilon)-approximation algorithm for computing the integral and average Fréchet distance between two given polygonal curves T_1 and T_2. The running time is in O(zeta^{4}n^4/epsilon^2) where n is the complexity of T_1 and T_2 and zeta is the maximal ratio of the lengths of any pair of segments from T_1 and T_2.

Furthermore, we give relations between weighted shortest paths inside a single parameter cell C and the monotone free space axis of C. As a result we present a simple construction of weighted shortest paths inside a parameter cell. Additionally, such a shortest path provides an optimal solution for the partial Fréchet similarity of segments for all leash lengths. These two aspects are related to each other and are of independent interest.

BibTeX - Entry

@InProceedings{maheshwari_et_al:LIPIcs:2016:6048,
  author =	{Anil Maheshwari and J{\"o}rg-R{\"u}diger Sack and Christian Scheffer},
  title =	{{Approximating the Integral Fr{\'e}chet Distance}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6048},
  URN =		{urn:nbn:de:0030-drops-60485},
  doi =		{10.4230/LIPIcs.SWAT.2016.26},
  annote =	{Keywords: Fr{\'e}chet distance, partial Fr{\'e}chet similarity, curve matching}
}

Keywords: Fréchet distance, partial Fréchet similarity, curve matching
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI