ハウスドルフ距離

数学においてハウスドルフ距離（英: Hausdorff distance）とは距離空間の部分空間同士の隔たりを測る量の一種である。ハウスドルフ距離は1914年に出版されたフェリックス・ハウスドルフの著書集合論基礎に現れている。ただし、1906年のモーリス・ルネ・フレシェの博士論文に書かれた三次元空間内の連続曲線全体からなる空間の研究に非常によく似た類似物が登場している。

定義

距離空間 $(M, d)$ の空でない^{[注釈 1]}部分集合全体 ${\mathcal {P}}^{\times }(M)$ 上の拡張擬距離 $d_{\rm {H}}:{\mathcal {P}}^{\times }(M)\times {\mathcal {P}}^{\times }(M)\rightarrow \mathbb {R} _{\geq 0}\cup \{\infty \}$ を

d_{\rm {H}}(X,Y):={\rm {{max}\{\sup _{x\in X}d(x,Y),\sup _{y\in Y}d(y,X)\}}}

と定義する（ただし、 $X$ 、 $Y$ は距離空間 $(M, d))$ の任意の空でない部分集合で、 $d(x,Y):=\inf _{y\in Y}d(x,y)$ ）。 $d H$ をハウスドルフ距離という^[1]。

これは次のように表現することも出来る。

d_{\rm {H}}(X,Y)=\inf\{\epsilon >0:X\subseteq N_{\epsilon }(Y),Y\subseteq N_{\epsilon }(X)\}

ただし、 $N ε (X) := {p \in M : d(p,X) < ε}$

$d H (X, Y) = 0 \Leftrightarrow cl M (X) = cl M (Y)$ （ただし、 $cl M (X)$ は $X$ の閉包）なので、空でない閉集合全体は擬距離 $d H$ に関する同値類の完全代表系をなす。更に、 $X$ 、 $Y$ が有界集合なら明らかに $d H (X, Y)$ は有限である。以上から $d H$ は $M$ 上の空でない有界閉集合全体 ${\mathcal {B}}^{\times }(M)$ 上の距離となる。

自然な埋め込み $\iota :(M,d)\rightarrow ({\mathcal {B}}^{\times }(M),d_{\rm {H}})$ を $ι (x) := {x}$ と定義すると、 $ι$ は等長埋め込みになっていて、その像は閉集合。

ハウスドルフ距離は一様構造や粗構造といった距離構造の一般化にも自然に拡張できる。

性質

以下距離空間 $M$ を固定。

$p \in M$ 、 $X, Y \subseteq M$ のとき $d (p, Y) \leq d (p, X) + d H (X, Y)$ 。
$X, Y \subseteq M$ のとき $dia(Y) \leq dia(X) + 2\cdot d H (X, Y)$ （ただし、 $dia(X)$ は $X$ の直径）。
$X, Y \subseteq M$ について $X \cap Y$ の内部は空でないとする。このとき $Z \subseteq M$ と $X$ のハウスドルフ距離が十分小さければ、 $Z \cap Y \neq \emptyset$ 。
$X, Y, Z \subseteq M$ 、 $d H (X, Z) \leq a, d H (Z, Y) \leq b$ とする。このとき $Z \subseteq (⋂ r > a N r (X))\cap(⋂ r > b N r (Y))$ であり、 $(⋂ r > a N r (X))\cap(⋂ r > b N r (Y))$ は $d H (X, W) \leq a, d H (W, Y) \leq b$ 　を満たす最大の $W$ 。

部分集合の空間

$M$ を距離空間、 ${\mathcal {B}}^{\times }(M)$ をその上の空でない有界閉集合全体、 ${\mathcal {TB}}^{\times }(M)$ を空でない全有界閉集合全体、 ${\mathcal {K}}^{\times }(M)$ を空でないコンパクト部分集合全体、 ${\mathcal {P}}_{\rm {fin}}^{\times }(M)$ を空でない有限集合全体とする。

距離空間の空でない部分集合について、全有界であることと、ハウスドルフ距離の意味で有限集合の極限になることが同値（つまり ${\overline {{\mathcal {P}}_{\rm {fin}}^{\times }(M)}}={\mathcal {TB}}^{\times }(M)$ ）。
上からも明らかなように空でない全有界集合のハウスドルフ距離の意味での極限は全有界（つまり ${\mathcal {TB}}^{\times }(M)$ は閉）。
$M$ が完備なら ${\mathcal {B}}^{\times }(M)$ も完備（ $M$ は ${\mathcal {B}}^{\times }(M)$ の閉部分集合と見なせるので逆も真）。
${\mathcal {K}}^{\times }(M)$ 上のハウスドルフ距離から入る距離位相はヴィートリス位相と一致する。

以下 $M$ は完備距離空間とする^{[注釈 2]}。

距離の性質のハウスドルフ距離への遺伝
空間＼性質	有界	固有	コンパクト	可分	弧長	測地	固有かつ測地
${\mathcal {B}}^{\times }(M)$	◯	◯	◯	×	◯	×	◯
${\mathcal {K}}^{\times }(M)$	◯	◯	◯	◯	×	×	◯

類似物

変換群による変形

$M$ を距離空間、 $X, Y \subseteq M$ を部分集合 $G \subseteqIso(M)$ を $M$ の等長変換（の一部）からなる群とする。このとき

d_{{\rm {H}},G}(X,Y):=\inf _{\gamma \in G}\{d_{\rm {H}}(X,\gamma (Y))\}

は新たな（拡張擬）距離を定める。空間内で位置や向きを調整してハウスドルフ距離を出来るだけ小さくした場合の極限がこれに当たる。これは下記のグロモフ・ハウスドルフ距離と元のハウスドルフ距離の中間的なものである。

グロモフ・ハウスドルフ距離

→詳細は「グロモフ・ハウスドルフ収束」を参照

上の場合は固定した空間内で位置や向きを調整したが背景となる空間そのものを取り替えることで、2つの図形の形状の差のみを取り出したものがグロモフ・ハウスドルフ距離である。

応用

ハウスドルフ距離（特に変換群による変形を施したもの）や関連する距離コンピュータビジョンにおいて与えられて画像から前もって用意された見本となる形状を見つけ出すのに使われている。そこでは、まず与えられた画像からエッジ検出により二値画像を出力し、見本をその画像内で調節することで2つのハウスドルフ距離が最小に（ないしそれに十分近く）なるような配置を見つけ出す。見本が配置された領域が形状が存在する最良の候補となる。更にコンピュータグラフィックスでは三次元の物体の表現の間の差異を測るためにも使われている。

注釈

^ 空集合にも定義できるが空集合は孤立点となり、集合族が良い性質を満たさなくなる。
^ このとき ${\mathcal {K}}^{\times }(M)={\mathcal {TB}}^{\times }(M)$

出典

^ Martin R.Bridson and André Haefliger, Metric Spaces of Non-positive Curvature,Springer,1999,p70-71

定義

性質

部分集合の空間

類似物

応用

注釈

出典

関連項目