|
КЛАССИФИКАТОР: метрическая геометрия
АВТОРЫ:
Иванов А.О., Тужилин А.А.
(A. O. Ivanov, A. A. Tuzhilin)
Расстояние Громова–Хаусдорфа, неприводимые соответствия, проблема
Штейнера и минимальные заполнения.
(Gromov-Hausdorff Distance, Irreducible Correspondences, Steiner
Problem, and Minimal Fillings.)
АННОТАЦИЯ:
Определены неприводимые соответствия, позволяющие эффективно
вычислять расстояние Громова-Хаусдорфа. С помощью неприводимых
соответствий показано, что семейство всех не более чем трехточечных
метрических пространств, наделенное метрикой Громова-Хаусдорфа,
изометрично многогранному конусу в пространстве R^3 с max-нормой.
Установлено, что в достаточно малых окрестностях трехточечных
метрических пространств со строгими неравенствами треугольника
минимальные деревья Штейнера в пространстве Громова-Хаусдорфа
являются минимальными заполнениями, т.е. их длину нельзя уменьшить,
если граничное множество изометрично вложить в какое-нибудь другое
объемлющее пространство. Построен пример трехточечной границы,
состоящей из трехточечных пространств, для которой минимальное
дерево Штейнера в пространстве Громова-Хаусдорфа не является
минимальным заполнением. Тем самым, показано, что суботношение
Штейнера пространства Громова-Хаусдорфа меньше 1. Идея неприводимых
соответствий позволила написать существенно более быстрый алгоритм
вычисления расстояния Громова-Хаусдорфа между конечными метрическими
пространствами. С помощью численного эксперимента оценку сверху на
суботношение Штейнера удалось уточнить: оказывается, оно меньше 0.857.
We introduce irreducible correspondences that enables us to
calculate the Gromov--Hausdorff distances effectively. By means of
these correspondences, we show that the set of all metric spaces
each consisting of no more than 3 points is isometric to a
polyhedral cone in the space R 3 endowed with the maximum norm. We
prove that for any 3 -point
metric space such that all the triangle inequalities are strict in
it, there exists a neighborhood such that the Steiner minimal trees
(in Gromov-Hausdorff space) with boundaries from this neighborhood
are minimal fillings, i.e., it is impossible to decrease the lengths
of these trees by isometrically embedding their boundaries into any
other ambient metric space. On the other hand, we construct an
example of 3 -point boundary whose points are 3 -point
metric spaces such that its Steiner minimal tree in the
Gromov-Hausdorff space is not a minimal filling. The latter proves
that the Steiner subratio of the Gromov-Hausdorff space is less than
1. The irreducible correspondences enabled us to create a quick
algorithm for calculating the Gromov-Hausdorff distance between
finite metric spaces. We carried out a numerical experiment and
obtained more precise upper estimate on the Steiner subratio: we
have shown that it is less than 0.857.
Ссылка на статью
|
|
|
О проекте