Gromov-Frechet distance between curves

O. Berezsky; M. Zarichnyi

doi:10.15330/ms.50.1.88-92

The Gromov-Frechet distance is obtained from the Frechet distance between metric curves similarly as the Gromov-Hausdorff distance is obtained from the Hausdorff distance. We prove that the Gromov-Frechet space is separable and non-complete.

1. P.K. Agarwal, R.B. Avraham, H. Kaplan, M. Sharir, Computing the discrete FrЃLechet distance in subquadratic time, SIAM J. Comput., 43 (2014), №2, 429-449.

2. J. Alber, R. Niedermeier, On multidimensional curves with Hilbert property, Theory of Computing Systems, 33 (2000), №4, 295-312.

3. H. Alt, M. Buchin, Can we compute the similarity between surfaces? Discrete Comput. Geom., 43 (2010), №1, 78.99.

4. Alt H., Godau M. Computing the Frechet distance between two polygonal curves, Int. J. of Computational Geometry and Applications, 5 (1995), 75-91.

5. D. Burago, Yu. Burago, S. Ivanov, A course in metric geometry, AMS GSM 33, 2001.

6. D.A. Edwards, The structure of superspace, published in: Studies in Topology, Academic Press, 1975, 121-133.

7. M. Gromov, Groups of polynomial growth and expanding maps, Publications mathematiques I.H.E.S., 53, 1981.

8. M. FrЃLechet, Sur quelques points du calcul fonctionnel, Rendiconti del Circolo Mathematico di Palermo, 22 (1906), 1-74.

9. G.M. Ewing, Calculus of variations with applications, Dover Publ., 1985.

10. G. Rote, Computing the Frechet distance between piecewise smooth curves, Computational Geometry, 37 (2007), 162-174.

11. M.I. Schlesinger, E.V. Vodolazskiy, V.M. Yakovenko, Frechet similarity of closed polygonal curves, International Journal of Computational Geometry & Applications, 26, (2016), №1, 53-66.

12. C. Kuratowski, Quelques probl`emes concernant les espaces metriques non-separables, Fundamenta Mathematicae, 25 (1935), 534-545.

13. A. Mosig, M. Clausen, Approximately matching polygonal curves with respect to the FrЃLechet distance, Computational Geometry, 30 (2005), 113-127.

14. T. Eiter, H. Mannila, Computing discrete Frechet distance, Technical Report CDTR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994.

15. Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, Antoine Vigneron, Computing the discrete Frechet distance with imprecise input, International Journal of Computational Geometry & Applications, 22 (2012), №1, 27-44.

16. K. Buchin, M. Buchin, C. Wenk, Computing the Frechet distance between simple polygons, Computational Geometry, 41 (2008), 2-20.

17. A.F. Cook IV, A. Driemel, J. Sherette, C.Wenk, Computing the Frechet distance between folded polygons, Computational Geometry, 50 (2015), 1-16.

18. C. Villani, Topics in optimal transportation, Amer. Math. Soc., Providence, Rhode Island, 2000.

	Gromov-Frechet distance between curves
Author	O. Berezsky¹, M. Zarichnyi² ob@tneu.edu.ua¹, zarichnyi@yahoo.com² 1) Ternopil National Economic University, Ternopil, Ukraine; 2) Department of Mechanics and Mathematics Lviv National University, Lviv, Ukraine
Abstract	The Gromov-Frechet distance is obtained from the Frechet distance between metric curves similarly as the Gromov-Hausdorff distance is obtained from the Hausdorff distance. We prove that the Gromov-Frechet space is separable and non-complete.
Keywords	Gromov-Frechet distance; Gromov-Frechet space; Gromov-Hausdorff distance
DOI	doi:10.15330/ms.50.1.88-92
Reference	1. P.K. Agarwal, R.B. Avraham, H. Kaplan, M. Sharir, Computing the discrete FrЃLechet distance in subquadratic time, SIAM J. Comput., 43 (2014), №2, 429-449. 2. J. Alber, R. Niedermeier, On multidimensional curves with Hilbert property, Theory of Computing Systems, 33 (2000), №4, 295-312. 3. H. Alt, M. Buchin, Can we compute the similarity between surfaces? Discrete Comput. Geom., 43 (2010), №1, 78.99. 4. Alt H., Godau M. Computing the Frechet distance between two polygonal curves, Int. J. of Computational Geometry and Applications, 5 (1995), 75-91. 5. D. Burago, Yu. Burago, S. Ivanov, A course in metric geometry, AMS GSM 33, 2001. 6. D.A. Edwards, The structure of superspace, published in: Studies in Topology, Academic Press, 1975, 121-133. 7. M. Gromov, Groups of polynomial growth and expanding maps, Publications mathematiques I.H.E.S., 53, 1981. 8. M. FrЃLechet, Sur quelques points du calcul fonctionnel, Rendiconti del Circolo Mathematico di Palermo, 22 (1906), 1-74. 9. G.M. Ewing, Calculus of variations with applications, Dover Publ., 1985. 10. G. Rote, Computing the Frechet distance between piecewise smooth curves, Computational Geometry, 37 (2007), 162-174. 11. M.I. Schlesinger, E.V. Vodolazskiy, V.M. Yakovenko, Frechet similarity of closed polygonal curves, International Journal of Computational Geometry & Applications, 26, (2016), №1, 53-66. 12. C. Kuratowski, Quelques probl`emes concernant les espaces metriques non-separables, Fundamenta Mathematicae, 25 (1935), 534-545. 13. A. Mosig, M. Clausen, Approximately matching polygonal curves with respect to the FrЃLechet distance, Computational Geometry, 30 (2005), 113-127. 14. T. Eiter, H. Mannila, Computing discrete Frechet distance, Technical Report CDTR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994. 15. Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, Antoine Vigneron, Computing the discrete Frechet distance with imprecise input, International Journal of Computational Geometry & Applications, 22 (2012), №1, 27-44. 16. K. Buchin, M. Buchin, C. Wenk, Computing the Frechet distance between simple polygons, Computational Geometry, 41 (2008), 2-20. 17. A.F. Cook IV, A. Driemel, J. Sherette, C.Wenk, Computing the Frechet distance between folded polygons, Computational Geometry, 50 (2015), 1-16. 18. C. Villani, Topics in optimal transportation, Amer. Math. Soc., Providence, Rhode Island, 2000.
Pages	88-92
Volume	50
Issue	1
Year	2018
Journal	Matematychni Studii
Full text of paper	pdf
Table of content of issue	html