Document Open Access Logo

On Computing the k-Shortcut Fréchet Distance

Authors Jacobus Conradi , Anne Driemel

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.46.pdf
  • Filesize: 1.07 MB
  • 20 pages

Document Identifiers

Author Details

Jacobus Conradi
  • Department of Computer Science, Universität Bonn, Germany
Anne Driemel
  • Hausdorff Center for Mathematics, Universität Bonn, Germany

Funding

This work has been funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - AA 1111/2-2 (FOR 2535 Anticipating Human Behavior).

Cite As Get BibTex

Jacobus Conradi and Anne Driemel. On Computing the k-Shortcut Fréchet Distance. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.46

Abstract

The Fréchet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a min-max formulation that considers all direction-preserving continuous bijections of the two curves. Because of its susceptibility to noise, Driemel and Har-Peled introduced the shortcut Fréchet distance in 2012, where one is allowed to take shortcuts along one of the curves, similar to the edit distance for sequences. We analyse the parameterized version of this problem, where the number of shortcuts is bounded by a parameter k. The corresponding decision problem can be stated as follows: Given two polygonal curves T and B of at most n vertices, a parameter k and a distance threshold δ, is it possible to introduce k shortcuts along B such that the Fréchet distance of the resulting curve and the curve T is at most δ? We study this problem for polygonal curves in the plane. We provide a complexity analysis for this problem with the following results: (i) assuming the exponential-time-hypothesis (ETH), there exists no algorithm with running time bounded by n^o(k); (ii) there exists a decision algorithm with running time in O(k n^{2k+2} log n). In contrast, we also show that efficient approximate decider algorithms are possible, even when k is large. We present a (3+ε)-approximate decider algorithm with running time in O(k n² log² n) for fixed ε. In addition, we can show that, if k is a constant and the two curves are c-packed for some constant c, then the approximate decider algorithm runs in near-linear time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Fréchet distance
  • Partial similarity
  • Conditional lower bounds
  • Approximation algorithms

Metrics

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

Related Versions

References

  1. Amir Abboud and Kevin Lewi. Exact Weight Subgraphs and the k-Sum Conjecture. In Proceedings of the 40th International Conference on Automata, Languages, and Programming - Volume Part I, pages 1-12. Springer-Verlag, 2013. URL: https://doi.org/10.1007/978-3-642-39206-1_1.
  2. Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan, and Micha Sharir. Computing the Discrete Fréchet Distance in Subquadratic Time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 156-167. Society for Industrial and Applied Mathematics, 2013. URL: https://doi.org/10.1137/1.9781611973105.12.
  3. Hugo Alves Akitaya, Maike Buchin, Leonie Ryvkin, and Jérôme Urhausen. The k-Fréchet Distance: How to Walk Your Dog While Teleporting. In 30th International Symposium on Algorithms and Computation, volume 149, pages 50:1-50:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.50.
  4. Helmut Alt, Bernd Behrends, and Johannes Blömer. Approximate matching of polygonal shapes. Annals of Mathematics and Artificial Intelligence, 13:251-265, 1995. URL: https://doi.org/10.1007/BF01530830.
  5. Helmut Alt and Michael Godau. Computing the Fréchet Distance between Two Polygonal Curves. International Journal of Computational Geometry & Applications, 5:75-91, 1995. URL: https://doi.org/10.1142/S0218195995000064.
  6. Helmut Alt, Christian Knauer, and Carola Wenk. Comparison of Distance Measures for Planar Curves. Algorithmica, 38:45-58, 2003. URL: https://doi.org/10.1007/s00453-003-1042-5.
  7. Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk. Fréchet Distance for Curves, Revisited. In Proceedings of the 14th Conference on Annual European Symposium - Volume 14, pages 52-63. Springer-Verlag, 2006. URL: https://doi.org/10.1007/11841036_8.
  8. Rinat Ben Avraham, Omrit Filtser, Haim Kaplan, Matthew J. Katz, and Micha Sharir. The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection. ACM Transactions on Algorithms, 11(4):29:1-29:29, 2015. URL: https://doi.org/10.1145/2700222.
  9. Karl Bringmann. Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In 55th IEEE Annual Symposium on Foundations of Computer Science, pages 661-670, 2014. URL: https://doi.org/10.1109/FOCS.2014.76.
  10. Karl Bringmann and Marvin Künnemann. Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds. International Journal of Computational Geometry & Applications, 27(1-2):85-120, 2017. URL: https://doi.org/10.1142/S0218195917600056.
  11. Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete Fréchet distance. Journal of Computational Geometry, 7(2):46-76, 2016. URL: https://doi.org/10.20382/jocg.v7i2a4.
  12. Alexander M Bronstein, Michael M Bronstein, Alfred M Bruckstein, and Ron Kimmel. Partial Similarity of Objects, or How to Compare a Centaur to a Horse. International Journal of Computer Vision, 84(2):163, 2009. URL: https://doi.org/10.1007/s11263-008-0147-3.
  13. Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer. Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance. Discrete & Computational Geometry, 58(1):180-216, 2017. URL: https://doi.org/10.1007/s00454-017-9878-7.
  14. Kevin Buchin, Maike Buchin, and Yusu Wang. Exact algorithms for partial curve matching via the Fréchet distance. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 645-654. Society for Industrial and Applied Mathematics, 2009. URL: https://doi.org/10.1137/1.9781611973068.71.
  15. Kevin Buchin, Tim Ophelders, and Bettina Speckmann. SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2887-2901, 2019. URL: https://doi.org/10.1137/1.9781611975482.179.
  16. Maike Buchin, Anne Driemel, and Bettina Speckmann. Computing the Fréchet distance with shortcuts is NP-hard. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, pages 367-376. Association for Computing Machinery, 2014. URL: https://doi.org/10.1145/2582112.2582144.
  17. Timothy M. Chan and Zahed Rahmati. An improved approximation algorithm for the discrete Fréchet distance. Information Processing Letters, 138:72-74, 2018. URL: https://doi.org/10.1016/j.ipl.2018.06.011.
  18. Connor Colombe and Kyle Fox. Approximating the (Continuous) Fréchet Distance. In 37th International Symposium on Computational Geometry, volume 189, pages 26:1-26:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.26.
  19. Jacobus Conradi and Anne Driemel. On Computing the k-Shortcut Fréchet Distance, 2022. URL: https://doi.org/10.48550/ARXIV.2202.11534.
  20. 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. Computational Geometry, 47(5):625-641, 2014. URL: https://doi.org/10.1016/j.comgeo.2014.01.002.
  21. Anne Driemel and Sariel Har-Peled. Jaywalking Your Dog: Computing the Fréchet Distance with Shortcuts. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 318-337. Society for Industrial and Applied Mathematics, 2012. URL: https://doi.org/10.1137/1.9781611973099.30.
  22. Anne Driemel, Sariel Har-Peled, and Carola Wenk. Approximating the Fréchet Distance for Realistic Curves in near Linear Time. In Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, pages 365-374. Association for Computing Machinery, 2010. URL: https://doi.org/10.1145/1810959.1811019.
  23. Leonidas Guibas, John Hershberger, Joseph Mitchell, and Jack Snoeyink. Approximating Polygons and Subdivisions with Minimum-Link Paths. In International Journal of Computational Geometry & Applications, volume 3, pages 151-162, 1994. URL: https://doi.org/10.1007/3-540-54945-5_59.
  24. Russell Impagliazzo and Ramamohan Paturi. The complexity of k-SAT. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, pages 237-240. IEEE Computer Society, 1999. URL: https://doi.org/10.1109/CCC.1999.766282.
  25. David Jacobs, Daphna Weinshall, and Yoram Gdalyahu. Classification with Nonmetric Distances: Image Retrieval and Class Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(6):583-600, 2000. URL: https://doi.org/10.1109/34.862197.
  26. Mihai Pătraşcu and Ryan Williams. On the Possibility of Faster SAT Algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1065-1075. Society for Industrial and Applied Mathematics, 2010. URL: https://doi.org/10.1137/1.9781611973075.86.
  27. Han Su, Shuncheng Liu, Bolong Zheng, Xiaofang Zhou, and Kai Zheng. A survey of trajectory distance measures and performance evaluation. The VLDB Journal, 29(1):3-32, 2020. URL: https://doi.org/10.1007/s00778-019-00574-9.
  28. R.C. Veltkamp. Shape matching: similarity measures and algorithms. In Proceedings International Conference on Shape Modeling and Applications, pages 188-197, 2001. URL: https://doi.org/10.1109/SMA.2001.923389.
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