LIPIcs.SoCG.2017.64.pdf
- Filesize: 411 kB
- 5 pages
Document
Folding Free-Space Diagrams: Computing the Fréchet Distance between 1-Dimensional Curves (Multimedia Contribution)
Authors
-
Part of:
Volume:
33rd International Symposium on Computational Geometry (SoCG 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-06-20
Cite AsGet BibTex
Kevin Buchin, Jinhee Chun, Maarten Löffler, Aleksandar Markovic, Wouter Meulemans, Yoshio Okamoto, and Taichi Shiitada. Folding Free-Space Diagrams: Computing the Fréchet Distance between 1-Dimensional Curves (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 64:1-64:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.64
https://doi.org/10.4230/LIPIcs.SoCG.2017.64
Abstract
By folding the free-space diagram for efficient preprocessing, we show that the Frechet distance between 1D curves can be computed in O(nk log n) time, assuming one curve has ply k.
Keywords
- Frechet distance
- ply
- k-packed curves
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. IJCGA, 5(1-2):78-99, 1995.
-
K. Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. 55th FOCS, pages 661-670, 2014.
-
K. Bringmann and M. Künnemann. Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. In Proc. 26th ISAAC, pages 517-528, 2015.
-
K. Bringmann and W. Mulzer. Approximability of the discrete fréchet distance. JoCG, 7(2):46-76, 2016.
-
K. Buchin, M. Buchin, W. Meulemans, and W. Mulzer. Four Soviets walk the dog: improved bounds for computing the Fréchet distance. DCG, 2017.
-
K. Buchin, M. Buchin, R. van Leusden, W. Meulemans, and W. Mulzer. Computing the Fréchet distance with a retractable leash. DCG, 56(2):315-336, 2016.
-
A. Driemel, S. Har-Peled, and C. Wenk. Approximating the Fréchet distance for realistic curves in near linear time. In Proc. 26th SoCG, pages 365-374, 2010.