Control Systems and Computers, N2-3, 2021, Article 2

https://doi.org/10.15407/csc.2021.02.020

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, waterlaz@gmail.com

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. Alt H., Godau M., 1995.”Computing the Fréchet distance between two polygonal curves”. Int. J. Comput. Geometry Appl.Vol. 5,pp. 75-91.
    https://doi.org/10.1142/S0218195995000064
  2. Berezsky O., Zarichnyi M., 2016. “Frechet distance between weighted rooted trees”.MatematychniStudii. Dec. Vol. 48.
    https://doi.org/10.15330/ms.48.2.165-170
  3. Berezsky O., Zarichnyi M., 2018. “Gromov-Frechet distance between metric curves”.MatematychniStudii. 2018. Aug. Vol. 50.
    https://doi.org/10.15330/ms.50.1.88-92
  4. Buchin M., Krivosija A., Neuhaus A., 2020.”Computing the Fréchet distance of trees and graphs of bounded tree width”.arXiv:2001.10502.
  5. Buchin K., 2017.”Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance”. Discrete & Computational Geometry.
    https://doi.org/10.1007/s00454-017-9878-7
  6. Lee T., Kashyap R., Chu, C., 1994.”Building Skeleton Models via 3-D Medial Surface Axis Thinning Algorithms”. CVGIP: Graphical Models and Image Processing. Vol. 56, no. 6,pp. 462-478.
    https://doi.org/10.1006/cgip.1994.1042
  7. Schlesinger M. I., Vodolazskiy E. V., Yakovenko V.M., 2016.”Frechet Similarity of Closed Polygonal Curves”. International Journal of Computational Geometry & Applications. Vol. 26, no. 01.
    https://doi.org/10.1142/S0218195916500035
  8. Zhang T. Y., Suen C. Y., 1984.”A Fast Parallel Algorithm for Thinning Digital Patterns.Commun. ACM. New York, NY, USA, Vol. 27, no. 3,pp. 236-239.
    https://doi.org/10.1145/357994.358023.

Received 01.06.2021