Document Open Access Logo

The k-Fréchet Distance: How to Walk Your Dog While Teleporting

Authors Hugo Alves Akitaya, Maike Buchin, Leonie Ryvkin, Jérôme Urhausen

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.50.pdf
  • Filesize: 0.73 MB
  • 15 pages

Document Identifiers

Author Details

Hugo Alves Akitaya
  • Department of Computer Science, Tufts University, Massachusetts, USA
Maike Buchin
  • Department of Mathematics, Ruhr University Bochum, Germany
Leonie Ryvkin
  • Department of Mathematics, Ruhr University Bochum, Germany
Jérôme Urhausen
  • Department of Information and Computing Sciences, Utrecht University, Netherlands

Funding

  • Alves Akitaya, Hugo: supported by NSF awards CCF-1422311 and CCF-1423615, and the Science Without Borders scholarship program.
  • Urhausen, Jérôme: supported by the Netherlands Organisation for Scientific Research under project 612.001.651.

Acknowledgements

We would like to thank Erik Demaine for contributing the key idea for proving hardness in the free space diagram in Section 3.1, as well as the organizers and other participants of the Intensive Research Program in Discrete, Combinatorial and Computational Geometry in Barcelona, 2018, for providing the perfect environment to meet other researchers.

Cite As Get BibTex

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 (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ISAAC.2019.50

Abstract

We introduce a new distance measure for comparing polygonal chains: the k-Fréchet distance. As the name implies, it is closely related to the well-studied Fréchet distance but detects similarities between curves that resemble each other only piecewise. The parameter k denotes the number of subcurves into which we divide the input curves (thus we allow up to k-1 "teleports" on each input curve). The k-Fréchet distance provides a nice transition between (weak) Fréchet distance and Hausdorff distance. However, we show that deciding this distance measure turns out to be NP-hard, which is interesting since both (weak) Fréchet and Hausdorff distance are computable in polynomial time. Nevertheless, we give several possibilities to deal with the hardness of the k-Fréchet distance: besides a short exponential-time algorithm for the general case, we give a polynomial-time algorithm for k=2, i.e., we ask that we subdivide our input curves into two subcurves each. We can also approximate the optimal k by factor 2. We then present a more intricate FPT algorithm using parameters k (the number of allowed subcurves) and z (the number of segments of one curve that intersect the epsilon-neighborhood of a point on the other curve).

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Fixed parameter tractability
Keywords
  • Measures
  • Fréchet distance
  • Hardness
  • FPT

Metrics

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

Related Versions

References

  1. Hugo A. Akitaya, Maike Buchin, Leonie Ryvkin, and Jérôme Urhausen. The k-Fréchet distance. CoRR, 2019. URL: http://arxiv.org/abs/1903.02353.
  2. Helmut Alt, Peter Braß, Michael Godau, Christian Knauer, and Carola Wenk. Computing the Hausdorff distance of geometric patterns and shapes. In Discrete and computational geometry, volume 25 of Algorithms Combin., pages 65-76. Springer, 2003. Google Scholar
  3. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. Internat. J. Comput. Geom. Appl., 5:75-91, 1995. Google Scholar
  4. Helmut Alt, Christian Knauer, and Carola Wenk. Comparison of distance measures for planar curves. Algorithmica, 38(1):45-58, 2004. Google Scholar
  5. Karl Bringmann. Why Walking the Dog Takes Time: Fréchet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 661-670, 2014. Google Scholar
  6. Kevin Buchin, Maike Buchin, Christian Knauer, Günther Rote, and Carola Wenk. How Difficult is it to Walk the Dog? In 23rd European Workshop on Computational Geometry (EuroCG), pages 170-173, 2007. Google Scholar
  7. Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer. Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance. Discrete and Computational Geometry, 58:180-216, 2017. Google Scholar
  8. 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, SODA '09, pages 645-654, 2009. Google Scholar
  9. Maike Buchin. On the Computability of the Fréchet Distance Between Triangulated Surfaces. PhD thesis, Free University Berlin, Institute of Computer Science, 2007. URL: http://www.diss.fu-berlin.de/diss/receive/FUDISS_thesis_000000002618.
  10. 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, SOCG'14, pages 367-376. ACM, 2014. URL: https://doi.org/10.1145/2582112.2582144.
  11. Maike Buchin and Leonie Ryvkin. The k-Fréchet distance of polygonal curves. In 34th European Workshop on Computational Geometry (EuroCG), 2018. URL: https://conference.imp.fu-berlin.de/eurocg18/.
  12. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015. Google Scholar
  13. Mark de Berg and Amirali Khosravi. Optimal binary space partitions for segments in the plane. Internat. J. Comput. Geom. Appl., 22:187-205, 2012. Google Scholar
  14. Anne Driemel and Sariel Har-Peled. Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts. CoRR, 2011. URL: http://arxiv.org/abs/1107.1720.
  15. Anne Driemel, Sariel Har-Peled, and Carola Wenk. Approximating the Fréchet distance for realistic curves in near linear time. Discrete and Computational Geometry, 48:94-127, 2012. Google Scholar
  16. Michael R. Garey and David S. Johnson. Computers and intractability. W. H. Freeman and Co., San Francisco, Calif., 1979. Google Scholar
  17. Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Minimum backward Fréchet distance. In Proceedings of the 22Nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL '14, pages 381-388. ACM, 2014. URL: https://doi.org/10.1145/2666310.2666418.
  18. Jacob E. Goodman, János Pach, and Chee-K. Yap. Mountain climbing, ladder moving, and the ring-width of a polygon. Amer. Math. Monthly, 96:494-510, 1989. Google Scholar
  19. Peter Schäfer. Untersuchungen zu Varianten des Fréchet-Abstands. Master’s thesis, Fernuniversität Hagen, 2019. Google Scholar
  20. Christian Scheffer. More Flexible Curve Matching via the Partial Fréchet Similarity. Int. J. Comput. Geometry Appl., 26:33-52, 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