Distance de Gromov-Hausdorff

En mathématiques, la distance de Gromov-Hausdorff quantifie la notion de proximité entre deux espaces métriques compacts. Elle constitue une variante et une généralisation de la distance de Hausdorff puisqu'elle permet une forme de comparaison à isométrie près entre espaces qui ne sont plus nécessairement des parties d'un espace ambiant.

La distance de Gromov–Hausdorff utilisée pour quantifier la proximité de forme pour des figures situées à des positions différentes : elle permet ici de réaliser un partitionnement de données.

Il s'agit effectivement d'une distance sur l'espace des classes d'isométrie d'espaces métriques compacts, appelé l'espace de Gromov-Hausdorff. La notion de convergence associée porte elle aussi le nom de convergence de Gromov-Hausdorff. Toutes ces notions ont été introduites en 1981 par Mikhail Gromov^[1], et la paternité lui en est très couramment attribuée^[2] même si on en trouve une première version dans un article de David Edawards de 1975^[3],[4]. Gromov l'a employée dans le domaine de la théorie géométrique des groupes pour établir un théorème sur les groupes à croissance polynomiale et en géométrie riemannienne pour établir un résultat de compacité des métriques vérifiant une certaine hypothèse de courbure (théorème de compacité de Gromov). Depuis lors, c'est un outil couramment employé dans ces deux domaines, mais qui trouve aussi des applications dans de nombreux autres, comme l'analyse d'images, la cosmologie^[5], l'étude de réseaux de neurones^[6].

Définition et premières propriétés

Distance entre deux espaces métriques compacts

La distance de Hausdorff est une recherche d'écart maximal entre deux figures, ici un disque et un carré.

La distance de Hausdorff est définie pour deux parties compactes X et Y d'un même espace métrique comme la plus grande distance entre un point d'une des deux parties et l'autre partie. Il est possible de formuler cela en termes d'inclusions d'ensembles, en introduisant le r-voisinage X_r d'une partie comme l'ensemble des points situés à distance inférieure à r de X. En effet la distance de Hausdorff s'écrit alors

${\displaystyle d_{H}(X,Y)=\min\{r\in \mathbb {R} _{+}\mid X\subset Y_{r}\quad {\text{et}}\quad Y\subset X_{r}\}.}$

La distance de Gromov-Hausdorff entre X et Y peut alors être définie en considérant tous les plongements isométriques possibles dans différents espaces tiers^[7] : ${\displaystyle d_{GH}(X,Y)}$ est la borne inférieure des ${\displaystyle d_{H}(f(X),g(Y))}$ pour tous les plongements isométriques de ${\displaystyle f:X\to Z,g:Y\to Z}$ dans un même espace métrique ${\displaystyle Z}$. Il apparaît clairement que la valeur obtenue ne dépend en fait que des classes d'isométrie de X et de Y.

On peut donner une formulation équivalente mais qui ne fait pas intervenir d'espace annexe : on définit pour cela la notion de r-approximation, qui est une sorte d'isométrie à r près : il s'agit d'une application ${\displaystyle f:X\to Y}$ telle que

- dans l'espace métrique Y on a ${\displaystyle [f(X)]_{r}=Y}$

- et ${\displaystyle \forall (x,x')\in X^{2},|d_{X}(x,x')-d_{Y}(f(x),f(x'))|<r}$.

Alors la distance de Gromov-Hausdorff entre X et Y est la borne inférieure des r pour lesquels il existe une r-approximation de X et Y et une autre de Y dans X^[2].

Espace de Gromov-Hausdorff

Les considérations précédentes amènent à travailler sur la notion de métrique à isométrie près. Sur l'ensemble ${\displaystyle {\mathfrak {Met}}}$ des classes d'isométrie d'espaces métriques compacts, on prouve que ${\displaystyle d_{GH}}$ réalise effectivement une distance (à valeurs finies)^[8]. Ce nouvel espace métrique est appelé espace de Gromov-Hausdorff, muni de la topologie de Gromov-Hausdorff. Il s'agit d'un espace complet et séparable^[9].

On peut définir la notion de convergence associée, soit pour les classes d'isométrie, soit pour les espaces métriques eux-mêmes : une suite d'espaces métriques ${\displaystyle (X_{n})}$ converge au sens de Gromov-Hausdorff vers un espace métrique ${\displaystyle X_{\infty }}$ si et seulement si ${\displaystyle d_{GH}(X_{n},X_{\infty })}$ tend vers 0. En ce cas, la limite est seulement unique à isométrie près. Par définition même, la convergence au sens de Hausdorff entraîne celle au sens de Gromov-Hausdorff.

Applications

L'ensemble des structures riemanniennes compactes forme une partie remarquable de ${\displaystyle ({\mathfrak {Met}},d_{GH})}$. Le théorème de compacité de Gromov montre le caractère précompact de l'ensemble des structures riemanniennes vérifiant une borne sur le diamètre et une certaine propriété de positivité de la courbure. Cela permet d'obtenir des résultats de convergence, et d'étudier les propriétés de continuité (ou d'effondrement) de diverses grandeurs géométriques, même si le passage à la limite fait sortir de la catégorie des variétés riemanniennes^[10].

Dans les domaines des mathématiques appliquées, la distance de Gromov-Hausdorff est utilisée pour analyser les correspondances des objets moyennant certains types d'invariances. L'exemple de base est la comparaison des parties de l'espace euclidien à isométrie près, mais plus généralement, d'autres types d'invariance peuvent être étudiés moyennant des choix de métrique judicieux. Dans le cas d'espaces métriques finis, cela conduit à la conception d'algorithmes de calcul, mais il s'agit de problèmes NP-difficiles^[11].

Notes et références

1. Gromov 1981
2. Berger 2003, p. 625
3. (en) David A. Edwards, « The Structure of Superspace », Studies in Topology, Academic Press,‎ 1975 (lire en ligne)
4. Who Invented the Gromov–Hausdorff Distance?, A. Tuzhilin, 2016
5. Friedmann cosmology and almost isotropy
6. Computing the Shape of Brain Networks Using Graph Filtration and Gromov-Hausdorff Metric
7. Burago, Burago et Ivanov 2001, p. 254
8. Burago, Burago et Ivanov 2001, p. 259.
9. (en) Petersen, P., Riemannian Geometry., Springer, 1998, chapitre 10.
10. (en) Jeff Cheeger et Tobias H. Colding, « On the structure of spaces with Ricci curvature bounded below. I », J. Differential Geom., vol. 46(3),‎ 1997, p. 406-480 (DOI 10.4310/jdg/1214459974)
11. (en) Facundo Mémoli, « Some Properties of Gromov–Hausdorff Distances », Discrete Comput Geom,‎ 2012 (lire en ligne)

Voir aussi

Bibliographie

• (en) Marcel Berger, A Panoramic View of Riemannian Geometry, 2003 [détail de l’édition]
• (en) D. Burago, Y. Burago et S. Ivanov, A Course in Metric Geometry, Amer. Math. Soc., coll. « Graduate Studies in Mathematics », 2001, chapitres 7 et suivants
• (en) Kenji Fukaya, « Hausdorff convergence of Riemannian manifolds andits applications », Recent topics in differential and analytic geometry, Academic Press,‎ 1990, p. 143-238
• Mikhail Gromov, Structures métriques pour les variétés riemanniennes, CEDIC, édité par J. Lafontaine et P. Pansu, 1981.
• (en) Mikhail Gromov, « Groups of Polynomial growth and Expanding Maps », Publications mathematiques I.H.É.S., vol. 53,‎ 1981

Article connexe

• Distance de Hausdorff

• Portail de la géométrie