Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Разделы

square Читателям

square Авторам

square Статьи

blank
Авторизация

       
blank
Поиск по указателям

blank
Красота
blank
blank
Электронный журнал

КЛАССИФИКАТОР: метрическая геометрия

АВТОРЫ:

Иванов А.О., Тужилин А.А.

(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.

Ссылка на статью
blank
Редколлегия
Главный редактор:
д. ф-м. н., проф., Чубариков В.Н.
Зам. главного редактора:
д. ф-м. н., проф., Мищенко А.С.
blank
HR
© Электронная библиотека попечительского совета мехмата МГУ, 2004-2017
Электронная библиотека мехмата МГУ | Valid HTML 4.01!| Valid CSS! О проекте