skip to main content
10.1145/3191801.3191811acmotherconferencesArticle/Chapter ViewAbstractPublication PagesiwiscConference Proceedingsconference-collections
research-article
Public Access

Fast fréchet distance between curves with long edges

Published: 12 April 2018 Publication History

Abstract

Computing Fréchet distance between two curves takes roughly quadratic time. The only strongly subquadratic time algorithm has been proposed in [7] for c-packed curves. In this paper, we show that for curves with long edges the Fréchet distance computations become easier. Let P and Q be two polygonal curves in Rd with n and m vertices, respectively. We prove three main results for the case when all edges of both curves are long compared to the Fréchet distance between them: (1) a linear-time algorithm for deciding the Fréchet distance between two curves, (2) an algorithm that computes the Fréchet distance in O((n + m) log(n + m)) time, and (3) a linear-time [EQUATION]-approximation algorithm for approximating the Fréchet distance between two curves.

References

[1]
2016. North America Migration Flyways. (sep 2016). https://www.nps.gov/pais/learn/nature/birds.htm
[2]
P.K. Agarwal, R.B. Avraham, H. Kaplan, and M. Sharir. 2014. Computing the Discrete Fréchet Distance in Subquadratic Time. SIAM J. Comput. 43 (2014), 429--449.
[3]
H. Alt and M. Godau. 1995. Computing the Fréchet Distance between two Polygonal Curves. International Journal of Computational Geometry and Applications 5, 1--2 (1995), 75--91.
[4]
K. Bringmann. 2014. Why Walking the Dog Takes Time: Fréchet Distance Has no Strongly Subquadtatic Algorithms unless SETH Fails. In Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS). 226--236.
[5]
K. Buchin, M. Buchin, C. Knauer, G. Rote, and C. Wenk. 2007. How difficult Is It to Walk you Dog?. In 32nd European Workshop on Computational Geometry. 170--173.
[6]
K. Buchin, M. Buchin, W. Meulemans, and W. Mulzer. 2014. Four Soviets Walk the Dog - with an Application to Alt's Conjecture. In Proceeding of the 25th ACM-SIAM Symposium on Discrete Algorithms. 1399--1413.
[7]
A. Driemel, S. Har-Peled, and C. Wenk. 2012. Approximating the Fréchet Distance for Realistic Curves in Near Linear Time. Discrete & Computational Geometry 48 (2012), 94--127.
[8]
A. Efrat, L.J. Guibas, S. Har-Peled, J.S.B Mitchell, and T.M. Murali. 2002. New Similarity Meaures between Polylines with Applicatons yo Morphing and Polygon Sweeping. Discrete & Computational Geometry 28, 4 (2002), 535--569.
[9]
J. Gudmundsson, P. Laube, and T. Wolle. 2007. Movement Pattern in Spatio Temporal Data (1st ed.). Springer-Verlag.
[10]
M. Jiang, Y. Xu, and B. Zhu. 2008. Protein Structure-Structure Alignment with Discrete Fréchet Distance. Journal of Bioinformatics and Computational Biology 6, 1 (2008), 51--64.
[11]
R. Sriraghavendra, K. Karthik, and C. Bhattacharyya. 2007. Fréchet Distance based Approach for Searching Online Handwrittien Documents. In In Proceeding of 9th International Conference on Document Analysis and Recognition. 461--465.

Cited By

View all
  • (2023)Comparison of electron density measurements from CSES and Swarm satellites with GNSS ionospheric tomography dataAdvances in Space Research10.1016/j.asr.2022.11.04071:6(2818-2832)Online publication date: Mar-2023
  • (2021)Translation Invariant Fréchet Distance QueriesAlgorithmica10.1007/s00453-021-00865-0Online publication date: 14-Aug-2021
  • (2019)Fast Fréchet Distance Between Curves with Long EdgesInternational Journal of Computational Geometry & Applications10.1142/S021819591950004329:02(161-187)Online publication date: 20-Sep-2019
  • Show More Cited By

Index Terms

  1. Fast fréchet distance between curves with long edges

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    IWISC '18: Proceedings of the 3rd International Workshop on Interactive and Spatial Computing
    April 2018
    118 pages
    ISBN:9781450354394
    DOI:10.1145/3191801
    © 2018 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of the United States government. As such, the United States Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 12 April 2018

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Fréchet distance
    2. approximation algorithm
    3. computational geometry
    4. polygonal curve

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    IWISC 2018

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)328
    • Downloads (Last 6 weeks)288
    Reflects downloads up to 06 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Comparison of electron density measurements from CSES and Swarm satellites with GNSS ionospheric tomography dataAdvances in Space Research10.1016/j.asr.2022.11.04071:6(2818-2832)Online publication date: Mar-2023
    • (2021)Translation Invariant Fréchet Distance QueriesAlgorithmica10.1007/s00453-021-00865-0Online publication date: 14-Aug-2021
    • (2019)Fast Fréchet Distance Between Curves with Long EdgesInternational Journal of Computational Geometry & Applications10.1142/S021819591950004329:02(161-187)Online publication date: 20-Sep-2019
    • (2018)Adaptive Computation of the Discrete Fréchet DistanceString Processing and Information Retrieval10.1007/978-3-030-00479-8_5(50-60)Online publication date: 14-Sep-2018

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media