Gromov-Hausdorff距離

Gromov-Hausdorff距離(グロモフ-ハウスドルフきょり、Gromov Hausdorff metric)とは、距離空間どうしの類似度を測る指標のひとつである。

定義

Hausdorff距離について復習する。

距離空間 $(X, d)$ のその部分集合 $A$ , $B$ について、Hausdorff距離 $d_{H} (A, B)$ を $m a x (sup_{a \in A} (d (a, B)), sup_{b \in B} (d (b, A)))$ として定義する。

Hausdorff距離は $P (M) ∖ {\emptyset}$ 上の拡張擬距離となっている。これは異なる元 $A, B$ についても $d (A, B) = 0$ となることを許し、また距離として無限大の値も許すということを意味する。

以上の準備のもと、Gromov-Hausdorff距離は以下のように定義される。

距離空間 $(X, d_{X})$ と $(Y, d_{Y})$ について、Gromov-Hausdorff距離 $d_{G H} (X, Y)$ とは、以下で定義される(無限大を許す)実数のことをいう:

距離空間 $M$ への等長写像 $f : X \to M$ , $g : Y \to M$ 全体をわたる、 $d_{H} (f (X), g (Y))$ の下限。