Fast fréchet distance between curves with long edges

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 R^d 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.

Index Terms

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry