Document Open Access Logo

Approximating the Integral Fréchet Distance

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

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.26.pdf
  • Filesize: 0.65 MB
  • 14 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Approximating the Integral Fréchet Distance. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SWAT.2016.26

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.

Subject Classification

Keywords
  • Fréchet distance
  • partial Fréchet similarity
  • curve matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geometry Appl., 5:75-91, 1995. URL: http://dx.doi.org/10.1142/S0218195995000064.
  2. Kevin Buchin, Maike Buchin, Wouter Meulemans, and Bettina Speckmann. Locally correct Fréchet matchings. In Leah Epstein and Paolo Ferragina, editors, ESA, volume 7501 of Lecture Notes in Computer Science, pages 229-240. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33090-2_21.
  3. Kevin Buchin, Maike Buchin, and Yusu Wang. Exact algorithms for partial curve matching via the Fréchet distance. In Claire Mathieu, editor, SODA, pages 645-654. SIAM, 2009. URL: http://dx.doi.org/10.1137/1.9781611973068.
  4. Maike Buchin. On the computability of the Fréchet distance between triangulated surfaces. Ph.D. thesis, Dept. of Comput. Sci., Freie Universität, Berlin, 2007. Google Scholar
  5. Jean-Lou De Carufel, Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Similarity of polygonal curves in the presence of outliers. Comput. Geom., 47(5):625-641, 2014. Google Scholar
  6. Isabel F. Cruz, Craig A. Knoblock, Peer Kröger, Egemen Tanin, and Peter Widmayer, editors. SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems (formerly known as GIS), SIGSPATIAL'12, Redondo Beach, CA, USA, November 7-9, 2012. ACM, 2012. Google Scholar
  7. Alon Efrat, Quanfu Fan, and Suresh Venkatasubramanian. Curve matching, time warping, and light fields: New algorithms for computing similarity between curves. Journal of Mathematical Imaging and Vision, 27(3):203-216, 2007. URL: http://dx.doi.org/10.1007/s10851-006-0647-0.
  8. Stefan Funke and Edgar A. Ramos. Smooth-surface reconstruction in near-linear time. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA., pages 781-790, 2002. Google Scholar
  9. Joachim Gudmundsson, Patrick Laube, and Thomas Wolle. Movement patterns in spatio-temporal data. In Shashi Shekhar and Hui Xiong, editors, Encyclopedia of GIS, pages 726-732. Springer, 2008. URL: http://dx.doi.org/10.1007/978-0-387-35973-1_823.
  10. Joachim Gudmundsson and Nacho Valladares. A GPU approach to subtrajectory clustering using the Fréchet distance. In Cruz et al. [6], pages 259-268. URL: http://dx.doi.org/10.1145/2424321.2424355.
  11. Joachim Gudmundsson and Thomas Wolle. Football analysis using spatio-temporal tools. In Cruz et al. [6], pages 566-569. URL: http://dx.doi.org/10.1145/2424321.2424417.
  12. Lawrence R. Rabiner and Biing-Hwang Juang. Fundamentals of speech recognition. Prentice Hall Signal Processing series. Prentice Hall, 1993. Google Scholar
  13. Günter Rote. Lexicographic fréechet matchings. In Proceedings of the 32st European Workshop on Computational Geometry, pages 101-104, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact