Document Open Access Logo

Approximating the (Continuous) Fréchet Distance

Authors Connor Colombe, Kyle Fox

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.26.pdf
  • Filesize: 0.79 MB
  • 14 pages

Document Identifiers

Author Details

Connor Colombe
  • The University of Texas at Austin, TX, USA
Kyle Fox
  • The University of Texas at Dallas, Richardson, TX, USA

Acknowledgements

Most of this work was done while the first author was a student at the University of Texas at Dallas. The authors would like to thank Karl Bringmann and Marvin Künnemann for some helpful discussions concerning turning an approximate decision procedure into a proper approximation algorithm.

Cite As Get BibTex

Connor Colombe and Kyle Fox. Approximating the (Continuous) Fréchet Distance. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SoCG.2021.26

Abstract

We describe the first strongly subquadratic time algorithm with subexponential approximation ratio for approximately computing the Fréchet distance between two polygonal chains. Specifically, let P and Q be two polygonal chains with n vertices in d-dimensional Euclidean space, and let α ∈ [√n, n]. Our algorithm deterministically finds an O(α)-approximate Fréchet correspondence in time O((n³ / α²) log n). In particular, we get an O(n)-approximation in near-linear O(n log n) time, a vast improvement over the previously best know result, a linear time 2^O(n)-approximation. As part of our algorithm, we also describe how to turn any approximate decision procedure for the Fréchet distance into an approximate optimization algorithm whose approximation ratio is the same up to arbitrarily small constant factors. The transformation into an approximate optimization algorithm increases the running time of the decision procedure by only an O(log n) factor.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Fréchet distance
  • approximation algorithm
  • approximate decision procedure

Metrics

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

Related Versions

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Proc. 56th Ann. IEEE Symp. Found. Comp. Sci., pages 59-78, 2015. Google Scholar
  2. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends: Or: a polylog shaved is a lower bound made. In Proc. 48th Ann. ACM Sympos. Theory of Comput., pages 375-388, 2016. Google Scholar
  3. Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan, and Micha Sharir. Computing the discrete Fréchet distance in subquadratic time. SIAM J. Comput., 43(2):429-449, 2014. Google Scholar
  4. Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying. Approximating dynamic time warping and edit distance for a pair of point sequences. In Proc. 32nd Int. Conf. Comput. Geom., pages 6:1-6:16, 2016. Google Scholar
  5. Mahmuda Ahmed, Sophia Karagiorgou, Dieter Pfoser, and Carola Wenk. Map Construction Algorithms. Springer, 2015. Google Scholar
  6. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geom. Appl., 5:75-91, 1995. Google Scholar
  7. Alexandr Andoni and Negev Shekel Nosatzki. Edit distance in near-linear time: it’s a constant factor. In Proc. 61st Ann. IEEE Symp. Found. Comput. Sci., 2020. Google Scholar
  8. Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk. Fréchet distance for curves, revisited. In Proc. 14th Ann. Euro. Sympos. Algo., pages 52-63, 2006. Google Scholar
  9. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput., 47(3):1087-1097, 2018. Google Scholar
  10. Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. 55th. Ann. IEEE Symp. Found. Comp. Sci., pages 661-670, 2014. Google Scholar
  11. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proc. 56th Ann. IEEE Symp. Found. Comp. Sci., pages 79-97, 2015. Google Scholar
  12. Karl Bringmann and Marvin Künnemann. Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. Int. J. Comput. Geom. Appl., 27(1-2):85-120, 2017. Google Scholar
  13. Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete Fréchet distance. J. Comput. Geom., 7(2):46-76, 2016. Google Scholar
  14. Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer. Four Soviets walk the dog: Improved bounds for computing the Fréchet distance. Discrete Comput. Geom., 58(1):180-216, 2017. Google Scholar
  15. Timothy M. Chan and Zahed Rahmati. An improved approximation algorithm for the discrete Fréchet distance. Inf. Process. Lett., 138:72-74, 2018. Google Scholar
  16. Daniel Chen, Anne Driemel, Leonidas J. Guibas, Andy Nguyen, and Carola Wenk. Approximate map matching with respect to the Fréchet distance. In Proc. 13th Meeting on Algorithm Engineering and Experiments, pages 75-83, 2011. Google Scholar
  17. Richard Cole. Slowing down sorting networks to obtain faster sorting algorithms. J. ACM, 34(1):200-208, 1987. Google Scholar
  18. Anne Driemel, Sariel Har-Peled, and Carola Wenk. Approximating the Fréchet distance for realistic curves in near linear time. Discrete Comput. Geom., 48(1):94-127, 2012. Google Scholar
  19. Kyle Fox and Xinyi Li. Approximating the geometric edit distance. In Proc. 30th Int. Symp. Algo. Comput., pages 26:1-26:16, 2019. Google Scholar
  20. Omer Gold and Micha Sharir. Dynamic time warping and geometric edit distance: Breaking the quadratic barrier. ACM Trans. Algorithms, 14(4):50:1-50:17, 2018. Google Scholar
  21. Joachim Gudmundsson, Majid Mirzanezhad, Ali Mohades, and Carola Wenk. Fast Fréchet distance between curves with long edges. Int. J. Comput. Geom. Appl., 29(2):161-187, 2019. Google Scholar
  22. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comp. Sys. Sci., 62(2):367-375, 2001. Google Scholar
  23. Minghui Jiang, Ying Xu, and Binhai Zhu. Protein structure-structure alignment with discrete Fréchet distance. J. Bioinformatics and Computational Biology, 6(1):51-64, 2008. Google Scholar
  24. William Kuszmaul. Dynamic time warping in strongly subquadratic time: Algorithms for the low-distance regime and approximate evaluation. In Proc. 46th Intern. Colloqu. Automata, Languages, Programming, pages 80:1-80:15, 2019. Google Scholar
  25. Nimrod Megiddo. Applying parallel computation algorithms in the design of serial algorithms. J. Assoc. Comput. Mach., 30(4):852-865, 1983. Google Scholar
  26. Majid Mirzanezhad. On the approximate nearest neighbor queries among curves under the Fréchet distance. CoRR, abs/2004.08444, 2020. URL: http://arxiv.org/abs/2004.08444.
  27. E. Sriraghavendra, K. Karthik, and Chiranjib Bhattacharyya. Fréchet distance based approach for searching online handwritten documents. In Proc. 9th Intern. Conf. Document Analysis and Recognition, pages 461-465, 2007. Google Scholar
  28. Rex Ying, Jiangwei Pan, Kyle Fox, and Pankaj K. Agarwal. A simple efficient approximation algorithm for dynamic time warping. In Proc. 24th ACM SIGSPATIAL Int. Conf. Adv. Geo. Inf. Sys., 2016. 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