Distance de Hausdorff

Imaginez deux dessins réduits à des nuages de points. Pour chaque point du premier, on cherche le point le plus proche dans le second. On garde ensuite le plus grand de ces petits trajets.

La distance de Hausdorff effectue aussi la recherche dans l'autre sens, puis retient le pire des deux résultats. Elle est donc petite seulement si aucun point de l'un des ensembles ne reste loin de l'autre. Un seul point isolé peut suffire à l'augmenter.

Soit un espace métrique X, muni d'une distance d. Pour un point x et une partie non vide E, la distance de x à E est la borne inférieure des distances de x aux points de E. Soient maintenant A et B deux parties compactes non vides de X.

La distance de Hausdorff, notée d_H, prend la plus grande des deux distances dirigées :La première quantité repère le point de A le plus mal approché par B ; la seconde inverse les rôles. Leur maximum rend la mesure symétrique. Pour des ensembles finis, les bornes supérieures et inférieures sont de simples maximums et minimums.

Si E_r désigne le r-voisinage fermé de E, la même condition se lit ainsi :Sur les compacts non vides, d_H est bien une métrique. L'espace de ces compacts est complet lorsque l'espace métrique X est lui-même complet.

Dans le plan euclidien, prenons deux ensembles finis. Données : A contient les points (0 ; 0), (4 ; 0) et (0 ; 3). B contient les points (1 ; 1) et (4 ; 1). Les coordonnées sont exprimées dans la même unité.

1. Pour les trois points de A, les distances au point le plus proche de B valent respectivement √2, 1 et √5. La plus grande est donc √5.

2. Pour les deux points de B, les distances au point le plus proche de A valent respectivement √2 et 1. La plus grande est √2.

3. On compare les deux distances dirigées :La distance de Hausdorff vaut donc exactement √5 unités, soit environ 2,236 unités.

Le schéma relie les deux points qui réalisent les maxima dirigés. Il montre pourquoi le trajet de longueur √5 impose le résultat final.

Le contrôle se refait avec les carrés des longueurs : du point (0 ; 3) au point (1 ; 1), le déplacement est (1 ; −2), donc 1² + (−2)² = 5. Aucun autre minimum dirigé ne dépasse cette valeur.

Pour comparer deux nuages de points, on calcule pour chaque point son plus proche voisin dans l'autre nuage, dans les deux sens. La distance de Hausdorff convient quand l'écart le plus défavorable doit rester sous une tolérance donnée. Une mesure moyenne est préférable si quelques points isolés ne doivent pas gouverner le verdict.

Pour vérifier que deux compacts sont proches à r près, on contrôle deux inclusions : chacun doit entrer dans le r-voisinage de l'autre. Une inclusion unique ne suffit pas, car elle ne détecte pas un morceau supplémentaire du second ensemble.

Pour étudier une suite de compacts, d_H fournit une notion de convergence qui suit les ensembles eux-mêmes. Dans un espace ambiant complet, une suite de Cauchy de compacts non vides admet ainsi une limite compacte non vide.

Distance minimale entre deux ensembles. Elle cherche seulement le couple de points le plus proche. Dans l'exemple, cette distance vaut 1, alors que d_H(A,B) vaut √5 : le point (0 ; 3), resté loin de B, tranche.

Un point aberrant domine. Si tous les points se correspondent sauf un point situé à 100 unités de l'autre ensemble, d_H atteint au moins 100. Il faut conserver ce verdict pour une tolérance au pire cas, ou choisir une mesure robuste si cet isolé doit être atténué.

L'ensemble vide sort du domaine. La distance d'un point à l'ensemble vide n'est pas une distance finie utilisable dans la formule. Il faut donc travailler avec des compacts non vides, comme l'exige la définition.

La compacité garantit les bons objets. Pour des parties non bornées, la valeur peut devenir infinie ; pour des parties non fermées, deux ensembles distincts peuvent avoir une distance nulle. Il faut rester dans les compacts non vides, ou annoncer explicitement une extension de la notion.

La complétude n'est pas automatique. La métrique d_H existe sur les compacts non vides de tout espace métrique. En revanche, l'espace ainsi formé n'est complet que si l'espace ambiant est complet ; cette hypothèse doit être vérifiée avant d'invoquer une limite.

La distance de Hausdorff transforme des ensembles compacts en points d'un nouvel espace métrique. Cette construction permet d'étudier la convergence d'une suite de formes avec les outils ordinaires des espaces métriques.

La genèse des espaces métriques — Pour replacer la mesure entre compacts dans l'histoire et le langage général des espaces métriques.