Gromov--Hausdorff Distance, Irreducible Correspondences, Steiner Problem, and Minimal Fillings

preprint2016arXivOpen access

Abstract

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 33 points is isometric to a polyhedral cone in the space R3R^3 endowed with the maximum norm. We prove that for any 33-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 33-point boundary whose points are 33-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.8570.857.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.