Document Open Access Logo

Approximability of the Discrete Fréchet Distance

Authors Karl Bringmann, Wolfgang Mulzer

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.739.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Karl Bringmann
Wolfgang Mulzer

Cite As Get BibTex

Karl Bringmann and Wolfgang Mulzer. Approximability of the Discrete Fréchet Distance. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 739-753, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.739

Abstract

The Fréchet distance is a popular and widespread distance measure for point sequences and for curves. About two years ago, Agarwal et al [SIAM J. Comput. 2014] presented a new (mildly) subquadratic algorithm for the discrete version of the problem. This spawned a flurry of activity that has led to several new algorithms and lower bounds.

In this paper, we study the approximability of the discrete Fréchet distance. Building on a recent result by Bringmann [FOCS 2014], we present a new conditional lower bound that strongly subquadratic algorithms for the discrete Fréchet distance are unlikely to exist, even in the one-dimensional case and even if the solution may be approximated up to a factor of 1.399.

This raises the question of how well we can approximate the Fréchet distance (of two given d-dimensional point sequences of length n) in strongly subquadratic time. Previously, no general results were known. We present the first such algorithm by analysing the approximation ratio of a simple, linear-time greedy algorithm to be 2^Theta(n). Moreover, we design an alpha-approximation algorithm that runs in time O(n log n + n^2 / alpha), for any alpha in [1, n]. Hence, an n^epsilon-approximation of the Fréchet distance can be computed in strongly subquadratic time, for any epsilon > 0.

Subject Classification

Keywords
  • Fréchet distance
  • approximation
  • lower bounds
  • Strong Exponential Time Hypothesis

Metrics

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

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. 55th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 434-443, 2014. Google Scholar
  2. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Proc. 41st Internat. Colloq. Automata Lang. Program. (ICALP), volume 8572 of LNCS, pages 39-51, 2014. Google Scholar
  3. Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proc. 26th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 218-230, 2015. Google Scholar
  4. 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
  5. Helmut Alt. Personal communication. 2012. Google Scholar
  6. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. Internat. J. Comput. Geom. Appl., 5(1-2):78-99, 1995. Google Scholar
  7. Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. 55th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 661-670, 2014. Google Scholar
  8. Karl Bringmann and Marvin Künnemann. Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. arXiv:1408.1340, 2014. Google Scholar
  9. Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer. Four soviets walk the dog - with an application to Alt’s conjecture. In Proc. 25th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 1399-1413, 2014. Google Scholar
  10. Kevin Buchin, Maike Buchin, Rolf van Leusden, Wouter Meulemans, and Wolfgang Mulzer. Computing the Fréchet distance with a retractable leash. In Proc. 21st Annu. European Sympos. Algorithms (ESA), pages 241-252, 2013. Google Scholar
  11. Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM, 42(1):67-90, 1995. Google Scholar
  12. Thomas Eiter and Heikki Mannila. Computing Discrete Fréchet Distance. Technical Report CD-TR 94/64, Christian Doppler Laboratory, 1994. Google Scholar
  13. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Comput. Geom. Theory Appl., 5(3):165-185, 1995. Google Scholar
  14. Michael R. Garey and David S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman, 1979. Google Scholar
  15. Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. In Proc. 55th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 621-630, 2014. Google Scholar
  16. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. System Sci., 62(2):367-375, 2001. Google Scholar
  17. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity. J. Comput. System Sci., 63(4):512-530, 2001. Google Scholar
  18. Mihai Pătraşcu and Ryan Williams. On the possibility of faster SAT algorithms. In Proc. 21st Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 1065-1075, 2010. Google Scholar
  19. Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane. An improved exponential-time algorithm for k-sat. J. ACM, 52(3):337-364, 2005. Google Scholar
  20. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proc. 45th Annu. ACM Sympos. Theory Comput. (STOC), pages 515-524, 2013. Google Scholar
  21. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoret. Comput. Sci., 348(2):357-365, 2005. 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