Control Systems and Computers, N2-3, 2021, Стаття 8

Control Systems and Computers, 2021, Issue 2-3 (292-293), pp. 20-27.

UDC 519.6

Ye.V. VODOLAZSKIY Senior Research Associate,
International Research and Training Centre of Information
Technologies and Systems of the NAS and MES of Ukraine,
Glushkovave., 40, Kyiv, 03187, Ukraine,

A Modification of the Frechet Distance for Nonisomorphic Trees

The paper presents a modification of the Frechet distance for nonisomorphic trees. While the classical Frechet distance between nonisomorphic trees is undefined, a new measure called similarity of a tree to a reference tree is given that is defined for a wider class of trees. A polynomial-time algorithm is given to determine whether one tree’s similarity to another is less than a given number.

Download full text! (On English)

Keywords: computational geometry, Frechet distance, trees.

  1. 1.Matas, J., Chum, O., Urban, M. and Pajdla, T.,2004. Robust wide baseline stereo from maximally stable extremal regions.Image and Vision Computing, 22, p. 761–767.
  2. Marot, J., Caulier, Y., Kuleschov, A., Spinnler, K. and Bourennane, S., 2008. Contour detection for industrial image processing by means of level set methods.  Advanced Concepts for Intelligent Vision Systems, p. 655–663.
  3. Kass, M., Witkin, A. and Terzopoulos, D. Snakes: Active contour models, IEEE Proc, on Computer Vision and Pattern Recognition, 1, p. 321–331.
  4. Adamek, T. and O’Connor, N. 2003. Efficient contour-based shape representation and matching, Proceedings of the 5th ACM SIGMM International Workshop on Multimedia Information Retrieval, p. 138–143.
  5. Marvaniya, S.Simultaneous Part-Decomposition and Contour Matching using Dynamic Programming. 2013. PhD thesis, Indian Institute of Technology.
  6. Alt, H. and Godau, M. Computing the frechet distance between two polygonal curves. 1995. International Journal on Computational Geometry and Appication, 5, p. 75–91.
  7. Driemel, A., Har-Peled, S. and Wenk, C. Approximating the frechet distance for realistic curves in near linear time.2012.Discrete & Computational Geometry, 48, p. 94-127.
  8. Schlesinger, M., Vodolazskiy, E. and Yakovenko, V. Frechet similarity of closed polygonal curves. 2016.International Journal of Computational Geometry and Applications, 26, p. 53–66.
  9. Schlesinger, M., Vodolazskiy, E. and Yakovenko, V. Recognizing the similarity of polygons in a strengthened hausdorff metric. 2014.Cybernetics and Systems Analysis, 3, p. 174–187.

Received 01.06.2021