A Modification of the Frechet Distance for Nonnisomorphic 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 algor...
Збережено в:
| Дата: | 2021 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2021
|
| Назва видання: | Control systems & computers |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/181259 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | A Modification of the Frechet Distance for Nonnisomorphic Trees / Ye.V. Vodolazskiy // Control systems & computers. — 2021. — № 2-3. — С. 20–27. — Бібліогр.: 8 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-181259 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1812592022-04-21T20:39:21Z A Modification of the Frechet Distance for Nonnisomorphic Trees Vodolazskiy, Ye.V. Fundamental Problems in Computer Science 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 for determining whether similarity of one tree to another is less than a given number. Ціль статті. Необхідно розробити метод порівняння дерев, ідеологічно близький до метрики Фреше, але виз- начений для пар неізоморфних дерев. Результати. У статті запропоновано модифікацію метрики Фреше для неізоморфних дерев. Нова числова характеристика названа близькістю дерева до еталону і визначена в тому числі для деяких класів пар неізоморфних дерев. Запропоновано поліноміальний алгоритм розпізнавання того, що одне дерево є близьким до іншого з точністю до заданого числа. 2021 Article A Modification of the Frechet Distance for Nonnisomorphic Trees / Ye.V. Vodolazskiy // Control systems & computers. — 2021. — № 2-3. — С. 20–27. — Бібліогр.: 8 назв. — англ. DOI https://doi.org/10.15407/csc.2021.02.020 2706-8145 http://dspace.nbuv.gov.ua/handle/123456789/181259 519.6 en Control systems & computers Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Fundamental Problems in Computer Science Fundamental Problems in Computer Science |
| spellingShingle |
Fundamental Problems in Computer Science Fundamental Problems in Computer Science Vodolazskiy, Ye.V. A Modification of the Frechet Distance for Nonnisomorphic Trees Control systems & computers |
| description |
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 for determining whether similarity of one tree to another is less than a given number. |
| format |
Article |
| author |
Vodolazskiy, Ye.V. |
| author_facet |
Vodolazskiy, Ye.V. |
| author_sort |
Vodolazskiy, Ye.V. |
| title |
A Modification of the Frechet Distance for Nonnisomorphic Trees |
| title_short |
A Modification of the Frechet Distance for Nonnisomorphic Trees |
| title_full |
A Modification of the Frechet Distance for Nonnisomorphic Trees |
| title_fullStr |
A Modification of the Frechet Distance for Nonnisomorphic Trees |
| title_full_unstemmed |
A Modification of the Frechet Distance for Nonnisomorphic Trees |
| title_sort |
modification of the frechet distance for nonnisomorphic trees |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2021 |
| topic_facet |
Fundamental Problems in Computer Science |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/181259 |
| citation_txt |
A Modification of the Frechet Distance for Nonnisomorphic Trees / Ye.V. Vodolazskiy // Control systems & computers. — 2021. — № 2-3. — С. 20–27. — Бібліогр.: 8 назв. — англ. |
| series |
Control systems & computers |
| work_keys_str_mv |
AT vodolazskiyyev amodificationofthefrechetdistancefornonnisomorphictrees AT vodolazskiyyev modificationofthefrechetdistancefornonnisomorphictrees |
| first_indexed |
2025-07-15T22:06:42Z |
| last_indexed |
2025-07-15T22:06:42Z |
| _version_ |
1837752343027777536 |
| fulltext |
20 iSSN 2706-8145, системи керування та комп'ютери, 2021, № 2–3
doi https://doi.org/10.15407/csc.2021.02.020
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,
glushkov ave., 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 for determining whether similarity of one tree to another is less than a given
number.
Keywords: computational geometry, Frechet distance, trees.
Introduction
Many image processing methods involve selecting
contours on the image and processing those con-
tours with various algorithms such as computing
the Frechet distance between the selected contour
and the reference contour . Another common ap-
proach is to perform a so-called image skeletoniza-
tion [6, 8] instead of contour selection . Computing
the Frechet distance between curves, both open
and closed, is a relatively well researched prob-
lem [1, 3, 5, 7] . Since an image contour is always
some sort of a curve, comparing contours with the
Frechet metric does not impose much difficulty .
The skeleton of a simply connected binary image
is in some sense an acyclic set of points (a tree) .
Computing the Frechet distance between trees [4]
can be problematic since the metric is either unde-
fined or equals infinity for non-isomorphic trees,
depending on the point of view . An alternative for
the Frechet metric is known [2], which is essen-
tially a mixture of the Frechet distance between
polygonal lines and Hausdorff distance . With this
approach the distance between any pair of trees is
defined and finite . We propose another variation on
the Frechet distance that is also defined for noniso-
morphic pairs of trees and is ideologically closer to
the original Frechet metric, although the proposed
distance is not symmetric and is therefore not a
metric .
problem formulation
Let Г = (V, E) be an acyclic connected graph
(a tree) with a finite number of vertices V ⊂ Rk,
which are points in a k-dimensional linear space,
and a set of edges E ⊂ V × V . Each edge (u,v) ∈ V
defines a linear segment λ(u, v) = {α u + (1 - α)
v | α ∈ [0, 1]}, and the whole tree Г defines a
subset of points in Rk, the union of all linear seg-
ments ( )
( ),
λ ,
u v E
X u v
∈
= ∪ , which are called points of
the tree Г .
Definition 1. The Frechet distance between trees
Г
1
and Г
2
with their corresponding sets of points
X
1
and X
2
is
1 2( , ) inf max ( , ( ))
x X
f X X d x x
ϕ
ϕ
∈Φ ∈
=
iSSN 2706-8145, control systems and computers, 2021, № 2–3 21
A Modification of the Frechet Distance for Nonisomorphic Trees
where Ф is the set of all continuous bijections
between X
1
and X
2
.
Definition 2. The Hausdorff distance between
sets X and Y is the number
( ) ( ) ( ), max[max min , ,max min , ].
y Y x Xx X y Y
h X Y d x y d x y
∈ ∈∈ ∈
= (1)
The problem of the Frechet distance between
trees is immediately apparent from the definition,
since the value f(X
1
,X
2
) is only defined when the set
of continuous bijections�Ф is not empty . The set
�Ф is never empty when Г
1
and Г
2
are polygonal
lines . The same, however, can not be said for non-
isomorphic pairs of trees .
Examples of trees that have at least one
continuous bijection is given on Fig . 2, while
Fig . 2 gives an example of a pair of trees with no
continuous bijection .
The Frechet metric needs to be weakened in
order to be used on non-isomorphic trees . We do
so by not limiting ϕ to continuous bijections .
For any function ϕ: X
1
→ X
2
and a point
x
2
�∈ X
2
denote ϕ-1(x
2
) = {x
1
�∈ X
1
|
ϕ(x
1
)} the
preimage of x
2
�∈ X
2
. Note that ϕ-1(x
2
) in no way
implies that ϕ is an invertible function .
For any continuous function ϕ: X
1
→ X
2
an image
( )2 1φX X∗ ∗= of any connected subset 1 1X X∗ ⊂ is
also connected .
Definition 3. A function ϕ: X
1
→ X
2
is called
monotone if preimage ϕ-1(x
2
) of any point x
2
∈�X
2
is a connected set.
Fig. 2 . A pair of trees with no continuous bijection and undefined
Frechet distance
Fig. 1. An example of trees with non-empty Ф . For any of given pair of trees
the Frechet distance is defined and is finite
22 iSSN 2706-8145, системи керування та комп'ютери, 2021, № 2–3
E.V. Vodolazskiy
Definition 4. For a given number ε the set
X
1
is called ε–similar to the reference set X
2
, if a
continuous monotone function ϕ: X
1
→ X
2
exists
such that ϕ(X
1
)=X
2
and d(x
1
, ϕ (x
1
)) ≤ ε for all x
1
∈
X
1
.
Definition 5. Similarity δ(X
1
,X
2
) of the set X
1
to
the reference set X
2
is the exact lower bound on
such values ε that X
1
is ε–similar to X
2
.
The problem is to determine for given trees Г
1
,
Г
2
and a number ε whether X
1
is ε-similar to X
2
,
where X
1
and X
2
are the sets of points of Г
1
and Г
2
respectively .
General properties of set similarity
The relation of ε-similarity of X
1
to X
2
as well as
the function δ(X
1
,X
2
) of similarity is not symmetric
with respect to its arguments . Therefore, δ(X
1
,X
2
) is
not a metric . Nevertheless, it is ideologically close
to the Hausdorff and Frechet metrics and lies in
the middle of them in the sense of the following
theorem .
Theorem 1. Let h(X
1
,X
2
) be the Hausdorff
distance between X
1
and X
2
, let f(X
1
,X
2
) be the
Frechet distance between X
1
and X
2
.
For all X
1
and X
2
the following inequalities are
valid
h(X
1
,X
2
) ≤ δ (X
1
,X
2
) ≤ f (X
1
,X
2
) . (2)
The equality δ(X
1
,X
2
) = 0 holds if and only if
X
1
=X
2
.
Proof. We first prove that when f (X
1
,X
2
) =
= f *, the inequality δ(X
1
,X
2
) ≤ f * holds . Indeed,
the expression f(X
1
,X
2
) = f * means that for any
ε* > f * a continuous bijection ϕ*: X
1
↔ X
2
exists, such that for any x ∈ X
1
the inequality
d(x
1
, ϕ (x
1
)) ≤ ε* holds . Since ϕ*is continuous
and invertible, then according to Definition 3 it
is monotone and according to Definition 4 the
set X
1
is ε*–similar to X
2
for all ε* > f * . Therefore,
δ (X
1
,X
2
) ≤ f * ccording to Definition 5 .
We now prove that if δ(X
1
,X
2
) ≤ δ* then
h(X
1
,X
2
) ≤ δ* . The equality δ(X
1
,X
2
) = δ* means that
for any ε* < δ* there exists a monotone continuous
functions ϕ: X
1
→ X
2
such that for any x ∈ X
1
the
inequality d(x
1
, ϕ* (x
1
)) ≤ ε* holds . For a function
ϕ* there exists a function ψ*: X
1
→ X
2
such that
ψ*(x
2
) ∈ ϕ* (x
2
) and
d(x
1
, ϕ* (x
1
)) ≤ ε* for all x
1
∈ X
1
,
d(ψ*(x
2
), x
2
) ≤ ε* for all x
2
∈ X
2
.
From the inequalities it obviously follows that
min d(x
1
, x
2
) ≤ ε* for all x
1
∈ X
1
,
x
2
∈ X
2
min d(x
1
, x
2
) ≤ ε* for all x
2
∈ X
2
,
x
1
∈ X
1
max min d(x
1
, x
2
) ≤ ε* ,
x
1
∈ X
1
x
2
∈ X
2
max min d(x
1
, x
2
) ≤ ε* ,
x
2
∈ X
2
x
1
∈ X
1
and finally
max {max min d(x
1
, x
2
), max min d(x
1
, x
2
)} ≤ ε* .
x
1
∈ X
1
x
2
∈ X
2
x
2
∈ X
2
x
1
∈ X
1
According to Definition 2 the left-hand side
of the last inequality is the Hausdorff distance
h(X
1
,X
2
) . Since h(X
1
,X
2
) ≤ ε* for all ε* > δ*, then
h(X
1
,X
2
) ≤ δ* = δ(X
1
,X
2
) .
The last statement of the theorem
[δ(X
1
,X
2
) = 0] ⇔ [X
1
= X
2
]
directly follows from the proved inequalities (2)
and the fact that both h and f are metrics .
properties of tree similarity
Let ,V EΓ = � be a tree that defines a set of points X .
Definition 6. Denote P(u,v)⊆ X the minimal
connected subset of X that contains u and v.
Definition 7. A point u ∈ V ⊂ Rk is called a bran-
ching point of X if u has strictly more than two adja-
cent vertices . A point u ∈ V ⊂ Rk is called a terminal
point of X if u has exactly one adjacent vertex . All
other points from X are called ordinary points .
iSSN 2706-8145, control systems and computers, 2021, № 2–3 23
A Modification of the Frechet Distance for Nonisomorphic Trees
A path P(u,v) can either go through branching
points of X or not . If all points r ∈ P(u,v)\{u,v}
are not branching points the path is called an
unbranched section (see Fig . 4) .
Definition 8. For any unbranched section
P(u,v) denote S(u,v) the set of such points t that
P(t,u)∩ P(u,v) = {u} and call it a sector (see
Fig . 4) .
Any terminal vertex is a special case of a sector .
Definition 9. For any pair of r ∈ V and s ∈ V
such that each r and s are either branching points
or terminals denote the set Z(r,s)=(X
\
S(r,u))
\
\ S(s,v) ∪ {r,s}, where u and v are branching points
on P(r,s) (see Figure 4) and call it a subtree of X .
Obviously P(r,s) ⊆ Z(r,s) is part of the subtree
Z(r,s) without all the branches .
Definition 10. A flower F(u,v) is the union of the
corresponding unbranched path and the sector .
F(u,v)=S(u,v) ∪P(u,v) .
The provided definitions result in a number of
properties .
Let r be a terminal point and let s be a branching
point such that P(r,s) is an unbranched section .
Then S(r,s) = {r} and S(s,r) ∪ P(r,s) = X . Or even
more general .
Property 1. If P(u,v) is an unbranched section
(see Fig . 4), then
X=S(u,v)∪P(u,v)∪S(v,u) .
Any sector that is not a terminal vertex is a union
of flowers as the following property states .
Property 2. Let S(u,v) be a sector and let {t
1
,
t
2
, . . ., t
n-1
, t
n
} be the set of all branching t
i
∈ S(u,v)
such that P(t
i
,u) is an unbranched section . In this
case (Fig . 4) sector S(u,v) can be expressed as
Fig. 4 . An example of sector S(u,v), which is a union of
sectors S(t
1
,u), S(t
2
,u), S(t
3
,u) and unbranched sections
P(t
1
,u), P(t
2
,u), P(t
3
,u) . Also F(t
1
,u) = S(t
1
,u) ∪ P(t
1
,u),
F(t
2
,u) = S(t
2
,u) ∪ P(t
2
,u) and F(t
3
,u) = S(t
3
,u) ∪ P(t
3
,u)
Fig. 3 . An example of an unbranched
section P(u,v) and two sectors S(u,v) and
S(v,u) that together form the whole set X
1
1
( , ) [ ( , ) ( , )]
[ ( , )]
n
i
n
i
S u v S t u P t u
F t u
=
=
= =
=
∪ ∪
∪
24 iSSN 2706-8145, системи керування та комп'ютери, 2021, № 2–3
E.V. Vodolazskiy
So to sum up, a sector is a union of flowers while
each flower is a union of a sector and an unbran-
ched path .
For any sector S a single set of flowers F
1
, F
2
,…
…, F
n
exist that satisfy Property 2 . We may say that
secto S consists of flowers F
1
, F
2
,…, F
n
.
The main idea of the algorithm presented
further is that for certain subsets X
1
* ⊆ X
1
and
X
2
* ⊆ X
2
it is determined whether a continuo-
us monotone mapping ϕ : X
1
* → X
2
* exists, such
that
max d(x
1
, ϕ (x
1
)) ≤ ε .
x∈X
1
*
Whenever such mapping exists we would say that
X
1
* maps onto X
2
* and denote this as G(X
1
*, X
2
*) = 1 .
Otherwise, G(X
1
*, X
2
*) = 0 denotes that such map-
ping does not exist .
Algorithm Description
When X
1
and X
2
are points of trees Г
1
and Г
2
the
concept of monotone and continuous function
ϕ: X
1
→ X
2
has a very demonstrative interpretation
expressed in the following three lemmas .
Lemma 1. For a monotone continuous func-
tion ϕ : X
1
→ X
2
and any three points u,v,w ∈ X
1
such that w ∈ P(u,v) the relation ϕ(w) ∈ P(ϕ(u),
ϕ(v)) holds .
Proof. Let us show that when the function ϕ:
X
1
→ X
2
is continuous then either ϕ(w) ∈ P(ϕ(u),
ϕ(v)) or ϕ is not monotone . Denote r = med(ϕ(w),
ϕ(u), ϕ(v)) a median of points ϕ (w), ϕ(u), ϕ(v),
that is a point of intersection of paths P(ϕ(u),
ϕ(v)), P(ϕ(w), ϕ(v)) and P(ϕ(w),ϕ(u)) . Either the
equality r = ϕ (w) holds or inequality r ≠ ϕ(w) holds .
If r = ϕ (w) then ϕ(w)∈ P(ϕ(u), ϕ(v)) .
Suppose that r≠ ϕ(w) . Since the restriction of
function ϕ to P(u,w) is a continuous function,
the point w
1
∈ P(w,v), w
1
≠ w, exists such that
ϕ(w
1
) = r . The restriction of ϕ to P(w,v) is also a
continuous function, and therefore, there exists
a point w
2
∈ P(w,v), w
2
≠ w, such that ϕ(w
2
) = r .
Therefore, w
1
-1 ∈ ϕ(r), w
2
-1 ∈ ϕ(r), and the point
w, that belongs to P(w
1
,w
2
) does not belong
to ϕ-1(r), since ϕ(w) ≠ r . This means that the
preimage ϕ-1(r) is not connected and ϕ is not
monotone .
Lemma 2. If ϕ: X
1
→ X
2
is a monotone continuous
function then for any three points u,v,w ∈ X
1
the
equality ϕ(med(u,v,w))=med(ϕ(u), ϕ(v), ϕ(w))
holds .
Proof. Median r of the triple u,v,w ∈ X
1
belongs
to paths P(u,v), P(u,w) and P(v,w) . Therefore,
according to Lemma 1, the point ϕ(r) belongs to
paths P((u), (v)), P(ϕ(u), ϕ(w)) and P(ϕ(v), ϕ(w)),
or in other words is a median of three points ϕ(u),
ϕ(v), ϕ(w) ∈ X
2
.
The algorithm works by determining whether
certain subsets X
1
* ⊆ X
1
of tree X
1
can be mapped
onto certain subsets X
2
* ⊆ X
2
of tree X
2
. Recall that
when such mapping exists it is denoted by G(X
1
*,
X
2
*) . Computing G(X
1
*, X
2
*) can be divided into
these important special cases .
Fig. 5 . A subtree Z(r,s) (shown in bold) is
a part of the whole tree X that is enclosed
between two sectors S(r,u) and S(s,v) such that
X = S(r, u) ∪ Z(r, s) ∪ S(r, v)
iSSN 2706-8145, control systems and computers, 2021, № 2–3 25
A Modification of the Frechet Distance for Nonisomorphic Trees
1 .Can a sector S(u,v) be mapped onto a sector
S(r,s) such that � ϕ(u) = r .
2 . Can a flower F(u,v) be mapped onto a flower
F(r,s) such that � ϕ(v) = s .
3 . Can a flower F(u,v) be mapped onto a single
point {r} .
4 . Can a subtree Z(u,v) be mapped onto an
unbranched path P(r,s) such that ϕ(u) = r and �
ϕ(v) = s .
Mapping a flower on a flower
A flower F(u,v) can be mapped onto a flower F(r,s)
if there exists a sector S(p,t) ⊂ F(u,v) that can be
mapped onto a sector S(r,s) such that the subtree
Z(p,v) can be mapped onto the unbranched section
P(r,s) (see Fig . 6) . This can be written as
( , )
( , ) ( , )
( , )
( ( , ), ( , ))
( ( , ), ( , )) & ( ( , ), ( , )).
S p t
S p t F u v
t P p v
G F u v F r s
G Z p v P r s G S p t S r s
⊂
∈
=
= ∨
Mapping a sector on a sector
If a sector
1
( , ) )
m
i
S u v F t u
=
= ∪ i( , is mapped onto a
sector
1
( , ) ( , )
n
i
i
S u v F p r
=
= ∪ via a function ϕ then
ϕ(u) = r and each flower F(t
i
, u), i = 1,..., m must
either map onto some flower F(p
i
, r) or map onto
the vertex r . Moreover, no two flowers can map on
the same flower, but multiple flowers can map onto
the vertex r . Whether such a correspondence exists
can be determined by solving a maximum matching
problem on a bipartite graph (see Fig . 7) .
Mapping a flower on a point
Testing whether G(F(t, u), r) = 1 is straightforward .
Indeed,
G(F(t, u), r) = 1 ⇔ ∀ x ∈ F(t, u) ∩ V
1
: d(x,r) ≤ ε,
so the algorithm needs to check the proximity of
finite number of points to r .
Mapping a subtree on an unbranched path
Testing G(Z(p, v), P(r, s)) = 1 may seem tricky .
However, it is not much different from testing
G(P(p, v), P(r, s)) = 1, which is the problem solved
by Alt and Godau [1] for testing whether the
Frechet distance between polygonal curves does
not exceed .
Fig. 6 . A flower F(u,v)=S(p,t)�∪ Z(p,v) (on the left)
being mapped onto a flower F(r,s)= S(r,s)�∪ P(r,s)
(on the right) . The subtree Z(p,v) and the unbranched
section P(r,s) are shown in bold
Fig. 7 . A maximum bipartite matching problem for com-
puting G(S(u,v),S(r,s)), when
1
( , ) )
m
i
S u v F t u
=
= ∪ i( ,
and
1
( , ) ( , )
n
i
i
S u v F p r
=
= ∪
26 iSSN 2706-8145, системи керування та комп'ютери, 2021, № 2–3
E.V. Vodolazskiy
Conclusions
We have presented a measure of similarity of one
tree to another reference tree . This measure of
similarity is not a metric, however, it is weaker
than the Frechet metric, which allows it to be fi-
nite on nonisomorphic trees, but stronger than the
Hausdorff metric .
The presented algorithm for determining if the
similarity between to trees is less than a given num-
ber ε takes polynomial time and works by reducing
the problem of comparing two trees into smaller
problems of comparing subsets of these trees (called
flowers and sectors), which in turn are reduced to
smaller and smaller problems and so on .
REFERENCES
Alt H ., Godau M ., 1995 .“Computing the Frechet distance between two polygonal curves” . Int . J . Comput . Geometry 1 .
Appl .Vol . 5,pp . 75–91 .
Berezsky O ., Zarichnyi M ., 2016 . “Frechet distance between weighted rooted trees” .MatematychniStudii . 2 .
Dec ., Vol . 48 .
Berezsky O ., Zarichnyi M ., 2018 . “Gromov-Frechet distance between metric curves” .MatematychniStudii . 2018 . 3 .
Aug ., Vol . 50 .
Buchin M ., Krivosija A ., Neuhaus A ., 2020 .“Computing the Frechet distance of trees and graphs of bounded tree 4 .
width” .arXiv:2001 . 10502 .
Buchin K ., 2017 .“Four Soviets Walk the Dog: Improved Bounds for Computing the Fr�chet Distance” . Discrete & 5 .
Computational Geometry .
Lee T ., Kashyap R ., Chu, C ., 1994 .“Building Skeleton Models via 3-D Medial Surface Axis Thinning Algorithms” . 6 .
CVGIP: Graphical Models and Image Processing . Vol . 56, no . 6, pp . 462–478 .
Schlesinger M . I ., Vodolazskiy E . V ., Yakovenko V .M ., 2016 .“Frechet Similarity of Closed Polygonal Curves” . 7 .
International Journal of Computational Geometry & Applications . Vol . 26, no . 01 .
Zhang T . Y ., Suen C . Y ., 1984 .“A Fast Parallel Algorithm for Thinning Digital Patterns .Commun . ACM . New York, NY, 8 .
USA, Vol . 27, no . 3, pp . 236–239 .
Received 01 .06 .2021
ЛІТЕРАТУРА
1 . Alt H ., Godau M . Computing the Frechet distance between two polygonal curves . Int . J . Comput . Geometry Appl .
1995 . Vol . 5 . P . 75–91 .
2 . Berezsky O ., ZarichnyiM .Frechet distance between weighted rooted trees .MatematychniStudii . 2016 . Dec . Vol . 48 .
3 . Berezsky O ., ZarichnyiM .Gromov-Frechet distance between metric curves .MatematychniStudii . 2018 . Aug . Vol . 50 .
4 . Buchin M ., Krivosija A ., Neuhaus A . Computing the Frechet distance of trees and graphs of bounded tree width .
arXiv:2001 .10502 . 2020 .
5 . Buchin K . Four Soviets Walk the Dog: Improved Bounds for Computing the Fr�chet Distance . Discrete & Computational
Geometry . 2017 .
6 . Lee T ., Kashyap R ., Chu C . Building Skeleton Models via 3-D Medial Surface Axis Thinning Algorithms . CVGIP:
Graphical Models and Image Processing . 1994 . Vol . 56, no . 6 . P . 462–478 .
7 . Schlesinger M . I ., Vodolazskiy E . V ., Yakovenko V . M .Frechet Similarity of Closed Polygonal Curves . International
Journal of Computational Geometry & Applications . 2016 . Vol . 26, no . 01 .
8 . Zhang T . Y ., Suen C . Y . A Fast Parallel Algorithm for Thinning Digital Patterns .Commun . ACM . New York, NY, USA,
1984 . Vol . 27, no . 3 . P . 236–239 .
Надійщла 01 .06 .2021
iSSN 2706-8145, control systems and computers, 2021, № 2–3 27
A Modification of the Frechet Distance for Nonisomorphic Trees
Є.В. Водолазський, старший науковий співробітник,
Міжнародний науково-навчальний центр
інформаційних технологій та систем НАН та МОН України,
03187, м . Київ, просп . Академіка Глушкова, 40, Україна,
waterlaz@gmail .com
МОДИФІКАЦІЯ МЕТРИКИ ФРЕШЕ ДЛЯ НЕІЗОМОРФНИХ ДЕРЕВ
Вступ . Скелетизація зображень для подальшого порівняння пар скелетів — поширена практика в розпізнаванні
зображень . У більшості випадків скелет зображення — ациклічна підмножина поля зору . Поширеною метрикою
для порівняння підмножин є метрика Фреше . Однак, відстань Фреше визначено лише для пар ізоморфних дерев,
що зводить нанівець можливість практично застосовувати таку метрику на деревах .
Ціль статті. Необхідно розробити метод порівняння дерев, ідеологічно близький до метрики Фреше, але виз-
начений для пар неізоморфних дерев .
Результати. У статті запропоновано модифікацію метрики Фреше для неізоморфних дерев . Нова числова ха-
рактеристика названа близькістю дерева до еталону і визначена в тому числі для деяких класів пар неізоморфних
дерев . Запропоновано поліноміальний алгоритм розпізнавання того, що одне дерево є близьким до іншого з
точністю до заданого числа .
Ключові слова: обчислювальна геометрія, метрика Фреше, дерева .
|