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.
- 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 - 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 - 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 - Buchin M., Krivosija A., Neuhaus A., 2020.”Computing the Fréchet distance of trees and graphs of bounded tree width”.arXiv:2001.10502.
- 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 - 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 - 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 - 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
