Document Open Access Logo

On the Discrete Fréchet Distance in a Graph

Authors Anne Driemel, Ivor van der Hoog, Eva Rotenberg

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.36.pdf
  • Filesize: 1.19 MB
  • 18 pages

Document Identifiers

Author Details

Anne Driemel
  • Hausdorff Center for Mathematics, Universität Bonn, Germany
Ivor van der Hoog
  • Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark
Eva Rotenberg
  • Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark

Funding

Partially supported by Independent Research Fund Denmark grants 2020-2023 (9131-00044B) "Dynamic Network Analysis".

Acknowledgements

We thank David Goeckede and Petra Mutzel for useful discussions.

Cite As Get BibTex

Anne Driemel, Ivor van der Hoog, and Eva Rotenberg. On the Discrete Fréchet Distance in a Graph. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.36

Abstract

The Fréchet distance is a well-studied similarity measure between curves that is widely used throughout computer science. Motivated by applications where curves stem from paths and walks on an underlying graph (such as a road network), we define and study the Fréchet distance for paths and walks on graphs. When provided with a distance oracle of G with O(1) query time, the classical quadratic-time dynamic program can compute the Fréchet distance between two walks P and Q in a graph G in O(|P|⋅|Q|) time. We show that there are situations where the graph structure helps with computing Fréchet distance: when the graph G is planar, we apply existing (approximate) distance oracles to compute a (1+ε)-approximation of the Fréchet distance between any shortest path P and any walk Q in O(|G|log|G|/√ε+|P|+|Q|/ε) time. We generalise this result to near-shortest paths, i.e. κ-straight paths, as we show how to compute a (1+ε)-approximation between a κ-straight path P and any walk Q in O(|G|log|G|/√ε+|P|+(κ|Q|)/ε) time. Our algorithmic results hold for both the strong and the weak discrete Fréchet distance over the shortest path metric in G.
Finally, we show that additional assumptions on the input, such as our assumption on path straightness, are indeed necessary to obtain truly subquadratic running time. We provide a conditional lower bound showing that the Fréchet distance, or even its 1.01-approximation, between arbitrary paths in a weighted planar graph cannot be computed in O((|P|⋅|Q|)^{1-δ}) time for any δ > 0 unless the Orthogonal Vector Hypothesis fails. For walks, this lower bound holds even when G is planar, unit-weight and has O(1) vertices.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Fréchet
  • graphs
  • planar
  • complexity analysis

Metrics

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

Related Versions

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 434-443. IEEE, 2014. Google Scholar
  2. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry & Applications, 5(01n02):75-91, 1995. Google Scholar
  3. Helmut Alt, Christian Knauer, and Carola Wenk. Comparison of distance measures for planar curves. Algorithmica, 38(1):45-58, 2004. Google Scholar
  4. Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk. Fréchet distance for curves, revisited. In European symposium on algorithms, pages 52-63. Springer, 2006. Google Scholar
  5. Alessandro Bombelli, Lluis Soler, Eric Trumbauer, and Kenneth D Mease. Strategic air traffic planning with Fréchet distance aggregation and rerouting. Journal of Guidance, Control, and Dynamics, 40(5):1117-1129, 2017. Google Scholar
  6. Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. In Proceedings of the 31st international conference on Very large data bases, pages 853-864, 2005. Google Scholar
  7. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless seth fails. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 661-670. IEEE, 2014. Google Scholar
  8. 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(01n02):85-119, 2017. Google Scholar
  9. Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete Fréchet distance. Journal of Computational Geometry, 7(2):46-76, 2016. Google Scholar
  10. Kevin Buchin, Maike Buchin, David Duran, Brittany Terese Fasy, Roel Jacobs, Vera Sacristan, Rodrigo I Silveira, Frank Staals, and Carola Wenk. Clustering trajectories for map construction. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 1-10, 2017. Google Scholar
  11. 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. Google Scholar
  12. 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. SIAM, 2009. Google Scholar
  13. 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. SIAM, 2019. Google Scholar
  14. Maike Buchin, Bernhard Kilgus, and Andrea Kölzsch. Group diagrams for representing trajectories. International Journal of Geographical Information Science, 34(12):2401-2433, 2020. Google Scholar
  15. Erin Wolf Chambers, Eric Colin De Verdiere, Jeff Erickson, Sylvain Lazard, Francis Lazarus, and Shripad Thite. Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time. Computational Geometry, 43(3):295-311, 2010. Google Scholar
  16. Timothy M Chan and Zahed Rahmati. An improved approximation algorithm for the discrete Fréchet distance. Information Processing Letters, 138:72-74, 2018. Google Scholar
  17. Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Almost optimal distance oracles for planar graphs. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 138-151. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316316.
  18. Vincent Cohen-Addad, Søren Dahlgaard, and Christian Wulff-Nilsen. Fast and compact exact distance oracle for planar graphs. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 962-973. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.93.
  19. Connor Colombe and Kyle Fox. Approximating the (continuous) Fréchet distance. In 37th International Symposium on Computational Geometry (SoCG 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  20. Thomas Devogele. A new merging process for data integration based on the discrete Fréchet distance. In Advances in spatial data handling, pages 167-181. Springer, 2002. Google Scholar
  21. Anne Driemel and Sariel Har-Peled. Jaywalking your dog: computing the Fréchet distance with shortcuts. SIAM Journal on Computing, 42(5):1830-1866, 2013. Google Scholar
  22. Anne Driemel, Sariel Har-Peled, and Carola Wenk. Approximating the Fréchet distance for realistic curves in near linear time. Discret. Comput. Geom., 48(1):94-127, 2012. URL: https://doi.org/10.1007/s00454-012-9402-z.
  23. Thomas Eiter and Heikki Mannila. Computing discrete Fréchet distance. Technical Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994. Google Scholar
  24. David Göckede. Computing the Fréchet distance in graphs efficiently using shortest-path distance oracles. Master’s thesis, Department of Computer Science, University of Bonn, 2021. Google Scholar
  25. Qian-Ping Gu and Gengchun Xu. Constant query time (1+ε)-approximate distance oracle for planar graphs. Theor. Comput. Sci., 761:78-88, 2019. URL: https://doi.org/10.1016/j.tcs.2018.08.024.
  26. Joachim Gudmundsson, Majid Mirzanezhad, Ali Mohades, and Carola Wenk. Fast Fréchet distance between curves with long edges. International Journal of Computational Geometry & Applications, 29(02):161-187, 2019. Google Scholar
  27. Atlas F Cook IV and Carola Wenk. Geodesic Fréchet distance inside a simple polygon. ACM Transactions on Algorithms (TALG), 7(1):1-19, 2010. Google Scholar
  28. Minghui Jiang, Ying Xu, and Binhai Zhu. Protein structure-structure alignment with discrete Fréchet distance. Journal of bioinformatics and computational biology, 6(01):51-64, 2008. Google Scholar
  29. Philip N. Klein. Preprocessing an undirected planar network to enable fast approximate distance queries. In David Eppstein, editor, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, pages 820-827. ACM/SIAM, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545488.
  30. Philip N. Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 146-155. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070454.
  31. Maximilian Konzack, Thomas McKetterick, Tim Ophelders, Maike Buchin, Luca Giuggioli, Jed Long, Trisalyn Nelson, Michel A Westenberg, and Kevin Buchin. Visual analytics of delays and interaction in movement data. International Journal of Geographical Information Science, 31(2):320-345, 2017. Google Scholar
  32. Yaowei Long and Seth Pettie. Planar distance oracles with better time-space tradeoffs. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2517-2537. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.149.
  33. Anil Maheshwari, Jörg-Rüdiger Sack, Kaveh Shahbaz, and Hamid Zarrabi-Zadeh. Fréchet distance with speed limits. Computational Geometry, 44(2):110-120, 2011. Google Scholar
  34. Ariane Mascret, Thomas Devogele, Iwan Le Berre, and Alain Hénaff. Coastline matching process based on the discrete Fréchet distance. In Progress in Spatial Data Handling, pages 383-400. Springer, 2006. Google Scholar
  35. Jiri Matousek. Lectures on discrete geometry, volume 212. Springer Science & Business Media, 2013. Google Scholar
  36. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, and Moti Yung, editors, Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 of Lecture Notes in Computer Science, pages 261-272. Springer, 2005. URL: https://doi.org/10.1007/11523468_22.
  37. Roniel S. De Sousa, Azzedine Boukerche, and Antonio A. F. Loureiro. Vehicle trajectory similarity: Models, methods, and applications. ACM Comput. Surv., 53(5), September 2020. URL: https://doi.org/10.1145/3406096.
  38. E Sriraghavendra, K Karthik, and Chiranjib Bhattacharyya. Fréchet distance based approach for searching online handwritten documents. In Ninth International Conference on Document Analysis and Recognition (ICDAR 2007), volume 1, pages 461-465. IEEE, 2007. Google Scholar
  39. 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. Google Scholar
  40. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM (JACM), 51(6):993-1024, 2004. Google Scholar
  41. Mikkel Thorup and Uri Zwick. Approximate distance oracles. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 183-192. ACM, 2001. URL: https://doi.org/10.1145/380752.380798.
  42. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023.
  43. Christian Wulff-Nilsen. Approximate distance oracles with improved query time. In Encyclopedia of Algorithms, pages 94-97. Springer, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_568.
  44. Dong Xie, Feifei Li, and Jeff M Phillips. Distributed trajectory similarity search. Proceedings of the VLDB Endowment, 10(11):1478-1489, 2017. 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