×

Fréchet distance between two point sets. (English) Zbl 1524.68402

Summary: We define and study the Fréchet distance and the discrete Fréchet distance between two point sets in the plane. One problem based on the well-known Fréchet distance is to find a polygonal curve on a point set with small Fréchet distance or small discrete Fréchet distance to another given polygonal curve. Here, we consider two given point sets and ask if permutations of these point sets exist, such that the Fréchet distance or the discrete Fréchet distance of curves defined by the permutations is small.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Accisano, P.; Üngör, A., Approximate matching of curves to point sets, (Proceedings of the 26th Canadian Conference on Computational Geometry (2014)), 443-450
[2] Accisano, P.; Üngör, A., Finding a curve in a point set (2014), CoRR
[3] Accisano, P.; Üngör, A., Matching curves to imprecise point sets using Fréchet distance (2014), CoRR
[4] Agarwal, P. K.; Avraham, R. B.; Kaplan, H.; Sharir, M., Computing the discrete Fréchet distance in subquadratic time, (Proceedings of the 24th Annual Symposium on Discrete Algorithms (2013)), 156-167 · Zbl 1422.68233
[5] Alt, H.; Behrends, B.; Blömer, J., Approximate matching of polygonal shapes (extended abstract), (Proceedings of the Seventh Annual Symposium on Computational Geometry (1991), Association for Computing Machinery: Association for Computing Machinery New York, NY, USA), 186-193
[6] Alt, H.; Godau, M., Computing the Fréchet distance between two polygonal curves, Int. J. Comput. Geom. Appl., 5, 1&2, 75-91 (1995) · Zbl 0941.68809
[7] Arora, S., Polynomial time approximation schemes for Euclidean TSP and other geometric problems, (Proceedings of the 37th Annual Symposium on Foundations of Computer Science. Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS ’96 (1996), IEEE Computer Society: IEEE Computer Society USA), 2
[8] Berman, P.; Karpinski, M.; Scott, A. D., Approximation Hardness of Short Symmetric Instances of MAX-3SAT, Electronic Colloquium on Computational Complexity (2003)
[9] Bringmann, K., Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails, (2014 IEEE 55th Annual Symposium on Foundations of Computer Science (2014)), 661-670
[10] Buchin, K.; Buchin, M.; Meulemans, W.; Mulzer, W., Four soviets walk the dog: improved bounds for computing the Fréchet distance, Discrete Comput. Geom., 58, 1, 180-216 (2017) · Zbl 1379.68319
[11] Buchin, M.; Kilgus, B., Fréchet distance between two point sets, (Proceedings of the 32nd Canadian Conference on Computational Geometry (2020)), 249-257
[12] Eiter, T.; Mannila, H., Computing discrete Fréchet distance (1994), Technical report
[13] Eiter, T.; Mannila, H., Distance measures for point sets and their computation, Acta Inform., 34, 2, 109-133 (Feb 1997) · Zbl 0865.51011
[14] Maheshwari, A.; Sack, J.-R.; Shahbaz, K.; Zarrabi-Zadeh, H., Staying close to a curve, (Proceedings of the 23rd Canadian Conference on Computational Geometry (2011))
[15] Shamos, M. I.; Hoey, D., Geometric intersection problems, (17th Annual Symposium on Foundations of Computer Science. 17th Annual Symposium on Foundations of Computer Science, Houston, Texas, USA, 25-27 October 1976 (1976), IEEE Computer Society), 208-215
[16] van Leeuwen, J.; Schoone, A. A., Untangling a travelling salesman tour in the plane, (Mühlbacher, J. R., Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG ’81). Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG ’81), Linz, Austria, June 15-17, 1981 (1981), Hanser: Hanser Munich), 87-98 · Zbl 0553.90103
[17] Wylie, T.; Zhu, B., Following a curve with the discrete Fréchet distance, Theor. Comput. Sci., 556, 34-44 (2014) · Zbl 1338.68272
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.