LIPIcs.SoCG.2024.10.pdf
- Filesize: 0.77 MB
- 14 pages
Document
Discrete Fréchet Distance Oracles
Authors
Boris Aronov 
,
Matthew J. Katz ,
Indu Ramesh
-
Part of:
Volume:
40th International Symposium on Computational Geometry (SoCG 2024)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2024-06-06
File
Document Identifiers
Author Details
- Department of Computer Science and Engineering, Tandon School of Engineering, New York University, Brooklyn, NY, USA
- Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Acknowledgements
We would like to thank an anonymous reviewer of an earlier version of this paper for a suggested improvement.
Cite As Get BibTex
Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh. Discrete Fréchet Distance Oracles. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
https://doi.org/10.4230/LIPIcs.SoCG.2024.10
Abstract
It is unlikely that the discrete Fréchet distance between two curves of length n can be computed in strictly subquadratic time. We thus consider the setting where one of the curves, P, is known in advance. In particular, we wish to construct data structures (distance oracles) of near-linear size that support efficient distance queries with respect to P in sublinear time. Since there is evidence that this is impossible for query curves of length Θ(n^α), for any α > 0, we focus on query curves of (small) constant length, for which we are able to devise distance oracles with the desired bounds. We extend our tools to handle subcurves of the given curve, and even arbitrary vertex-to-vertex subcurves of a given geometric tree. That is, we construct an oracle that can quickly compute the distance between a short polygonal path (the query) and a path in the preprocessed tree between two query-specified vertices. Moreover, we define a new family of geometric graphs, t-local graphs (which strictly contains the family of geometric spanners with constant stretch), for which a similar oracle exists: we can preprocess a graph G in the family, so that, given a query segment and a pair u,v of vertices in G, one can quickly compute the smallest discrete Fréchet distance between the segment and any (u,v)-path in G. The answer is exact, if t = 1, and approximate if t > 1.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- discrete Fréchet distance
- distance oracle
- heavy-path decomposition
- t-local graphs
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- P. K. Agarwal, R. Ben Avraham, H. Kaplan, and M. Sharir. Computing the discrete Fréchet distance in subquadratic time. SIAM J. Comput., 43(2):429-449, 2014. URL: https://doi.org/10.1137/130920526.
- H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geom. Appl., 5:75-91, 1995. URL: https://doi.org/10.1142/S0218195995000064.
- Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh. Discrete Fréchet distance oracles. arXiv, 2024. URL: https://doi.org/10.48550/arXiv.2404.04065.
- K. Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 661-670. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.76.
- K. Bringmann, M. Künnemann, and A. Nusser. Discrete Fréchet distance under translation: Conditional hardness and an improved algorithm. ACM Trans. Algorithms, 17(3):25:1-25:42, 2021. URL: https://doi.org/10.1145/3460656.
- K. Bringmann and W. Mulzer. Approximability of the discrete Fréchet distance. J. Comput. Geom., 7(2):46-76, 2016. URL: https://doi.org/10.20382/jocg.v7i2a4.
- K. Buchin, T. Ophelders, and B. Speckmann. SETH says: Weak Fréchet distance is faster, but only if it is continuous and in one dimension. In Timothy M. Chan, editor, Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2887-2901. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.179.
- M. Buchin, I. van der Hoog, T. Ophelders, L. Schlipf, R. I. Silveira, and F. Staals. Efficient Fréchet distance queries for segments. In 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 29:1-29:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ESA.2022.29.
-
S.-W. Cheng and H. Huang. Solving Fréchet distance problems by algebraic geometric methods. CoRR, abs/2308.14569, 2023.
-
M. de Berg, A. D. Mehrabi, and T. Ophelders. Data structures for Fréchet queries in trajectory data. In J. Gudmundsson and M. H. M. Smid, editors, Proceedings of the 29th Canadian Conference on Computational Geometry, CCCG 2017, July 26-28, 2017, Carleton University, Ottawa, Ontario, Canada, pages 214-219, 2017.
- A. Driemel and S. Har-Peled. Jaywalking your dog: Computing the Fréchet distance with shortcuts. SIAM J. Comput., 42(5):1830-1866, 2013. URL: https://doi.org/10.1137/120865112.
-
T. Eiter and H. Mannila. Computing discrete Fréchet distance. Technical Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994.
- A. Filtser and O. Filtser. Static and streaming data structures for Fréchet distance queries. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1150-1170. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.71.
- O. Filtser. Universal approximate simplification under the discrete Fréchet distance. Inf. Process. Lett., 132:22-27, 2018. URL: https://doi.org/10.1016/j.ipl.2017.10.002.
- J. Gudmundsson, M. P. Seybold, and S. Wong. Map matching queries on realistic input graphs under the Fréchet distance. In N. Bansal and V. Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 1464-1492. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch53.
- J. Gudmundsson and M. H. M. Smid. Fast algorithms for approximate Fréchet matching queries in geometric trees. Comput. Geom., 48(6):479-494, 2015. URL: https://doi.org/10.1016/J.COMGEO.2015.02.003.
- J. Gudmundsson, A. van Renssen, Z. Saeidi, and S. Wong. Translation invariant Fréchet distance queries. Algorithmica, 83(11):3514-3533, 2021. URL: https://doi.org/10.1007/s00453-021-00865-0.
- D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362-391, 1983. URL: https://doi.org/10.1016/0022-0000(83)90006-5.
- T. Wylie and B. Zhu. Protein chain pair simplification under the discrete Fréchet distance. IEEE ACM Trans. Comput. Biol. Bioinform., 10(6):1372-1383, 2013. URL: https://doi.org/10.1109/TCBB.2013.17.