Frechet distance between weighted rooted trees

O. Berezsky; M. Zarichnyi

doi:10.15330/ms.48.1.165-170

The aim of this note is to extend the notion of Frechet distance over the set of weighted rooted trees. The weighted trees naturally appear as skeletons of planar domains. The defined distance allows for defining a distance between (weighted) threes, which is merely a symmetric, i.e., does not necessarily satisfy the triangle inequality.

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

2. H. Alt, M. Buchin, Can we compute the similarity between surfaces? Discrete Comput. Geom., 43 (2010), №1, 78-99.

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

4. O. Berezsky, Frechet metric for trees, Proceedings of the 2016 IEEE First International Conference on Data Stream Mining & Processing (DSMP), Lviv, (2016), 213-217.

5. O. Berezsky, K. Berezska, Quantified estimation of image segmentation quality based on metrics, Upravlyayuschie sistemyi i mashinyi, 6 (2015), 59-65. (in Russian)

6. O. Berezsky, O. Pitsun, Automated processing of cytological and histological images, Proceedings of the XIIth International Conference Perspective Technologies and Methods in MEMS Design, MEMSTECHЃf2016, Lviv-Polyana, (2016), 51-53.

7. C.J. Bishop, H. Hakobyan, A central set of dimension 2, Proc. Amer. Math. Soc., 136 (2008), №7, 2453-2461.

8. E. Deza, M. Deza, Encyclopedia of distances, Springer, 2014.

9. D.H. Fremlin, Skeletons and central sets, Proc. London Math. Soc., 74 (1997), №3, 701-720.

10. M. Frechet, Sur quelques points du calcul fonctionnel, Rendiconti del Circolo Mathematico di Palermo, 22 (1906), 1-74.

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

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

13. 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.

14. L.J. Guibas, J.E. Hershberger, J.S.B. Mitchell, J.S. Snoeyink, Approximating polygons and subdivisions with minimum link paths, Internat. J. Comput. Geom. Appl., 3 (1993), №4, 383-415.

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

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

17. H.-K. Ahn, Ch. Knauer, M. Scherfenberg, L. Schlipf, A. Vigneron, Computing the discrete Frechet distance with imprecise input, International Journal of Computational Geometry & Applications, 22 (2012), №1, 27-44.

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

19. Atlas F. Cook I.V., A. Driemel, J. Sherette, C. Wenk, omputing the Frechet distance between folded polygons, Computational Geometry, 50 (2015), 1-16.

20. C. Villani, Topics in Optimal Transportation, Amer. Math. Soc., Providence, Rhode Island, 2000.

	Frechet distance between weighted rooted trees
Author	O. Berezsky, M. Zarichnyi ob@tneu.edu.ua; zarichnyi@yahoo.com Ternopil National Economic University, Ternopil, Ukraine; Department of Mechanics and Mathematics Ivan Franko National University of Lviv, Lviv, Ukraine
Abstract	The aim of this note is to extend the notion of Frechet distance over the set of weighted rooted trees. The weighted trees naturally appear as skeletons of planar domains. The defined distance allows for defining a distance between (weighted) threes, which is merely a symmetric, i.e., does not necessarily satisfy the triangle inequality.
Keywords	group; semigroup; maximal linked family; superextension; automorphism group
DOI	doi:10.15330/ms.48.2.165-170
Reference	1. P.K. Agarwal, R.B. Avraham, H. Kaplan, M. Sharir, Computing the discrete Frechet distance in subquadratic time, SIAM J. Comput., 43 (2014), №2, 429-449. 2. H. Alt, M. Buchin, Can we compute the similarity between surfaces? Discrete Comput. Geom., 43 (2010), №1, 78-99. 3. H. Alt, M. Godau, Computing the Frechet distance between two polygonal curves, Int. J. of Computational Geometry and Applications, 5 (1995), 75-91. 4. O. Berezsky, Frechet metric for trees, Proceedings of the 2016 IEEE First International Conference on Data Stream Mining & Processing (DSMP), Lviv, (2016), 213-217. 5. O. Berezsky, K. Berezska, Quantified estimation of image segmentation quality based on metrics, Upravlyayuschie sistemyi i mashinyi, 6 (2015), 59-65. (in Russian) 6. O. Berezsky, O. Pitsun, Automated processing of cytological and histological images, Proceedings of the XIIth International Conference Perspective Technologies and Methods in MEMS Design, MEMSTECHЃf2016, Lviv-Polyana, (2016), 51-53. 7. C.J. Bishop, H. Hakobyan, A central set of dimension 2, Proc. Amer. Math. Soc., 136 (2008), №7, 2453-2461. 8. E. Deza, M. Deza, Encyclopedia of distances, Springer, 2014. 9. D.H. Fremlin, Skeletons and central sets, Proc. London Math. Soc., 74 (1997), №3, 701-720. 10. M. Frechet, Sur quelques points du calcul fonctionnel, Rendiconti del Circolo Mathematico di Palermo, 22 (1906), 1-74. 11. G.M. Ewing, Calculus of variations with applications, Dover Publ., 1985. 12. G. Rote, Computing the Frechet distance between piecewise smooth curves, Computational Geometry, 37 (2007), 162-174. 13. 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. 14. L.J. Guibas, J.E. Hershberger, J.S.B. Mitchell, J.S. Snoeyink, Approximating polygons and subdivisions with minimum link paths, Internat. J. Comput. Geom. Appl., 3 (1993), №4, 383-415. 15. A. Mosig, M. Clausen, Approximately matching polygonal curves with respect to the Frechet distance, Computational Geometry, 30 (2005), 113-127. 16. T. Eiter, H. Mannila, Computing discrete Frechet distance, Technical Report CDTR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994. 17. H.-K. Ahn, Ch. Knauer, M. Scherfenberg, L. Schlipf, A. Vigneron, Computing the discrete Frechet distance with imprecise input, International Journal of Computational Geometry & Applications, 22 (2012), №1, 27-44. 18. K. Buchin, M. Buchin, C. Wenk, Computing the Frechet distance between simple polygons, Computational Geometry, 41 (2008), 2-20. 19. Atlas F. Cook I.V., A. Driemel, J. Sherette, C. Wenk, omputing the Frechet distance between folded polygons, Computational Geometry, 50 (2015), 1-16. 20. C. Villani, Topics in Optimal Transportation, Amer. Math. Soc., Providence, Rhode Island, 2000.
Pages	165-170
Volume	48
Issue	2
Year	2017
Journal	Matematychni Studii
Full text of paper	pdf
Table of content of issue	html