ハウスドルフ距離

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

定義

Components of the calculation of the Hausdorff distance between the green line X and the blue line Y.

距離空間 テンプレート:Math の空でない部分集合全体 ${𝒫}^{\times }(M)$ 上の拡張擬距離 $d_{\mathrm{H}}:{𝒫}^{\times }(M)\times {𝒫}^{\times }(M)\to {ℝ}_{\ge 0}\cup \{\mathrm{\infty }\}$ を

$d_{\mathrm{H}}(X,Y):=\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{\{}\underset{\mathrm{x}\mathrm{\in }\mathrm{X}}{\sup }\mathrm{d}\mathrm{(}\mathrm{x},\mathrm{Y}\mathrm{)},\underset{\mathrm{y}\mathrm{\in }\mathrm{Y}}{\sup }\mathrm{d}\mathrm{(}\mathrm{y},\mathrm{X}\mathrm{)}\mathrm{\}}$

と定義する（ただし、テンプレート:Math、テンプレート:Math は距離空間 テンプレート:Math の任意の空でない部分集合で、$d(x,Y):=\underset{y\in Y}{\inf }d(x,y)$ ）。テンプレート:Math をハウスドルフ距離という。

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

$d_{\mathrm{H}}(X,Y)=\inf \{ϵ>0:X\subseteq N_{ϵ}(Y),Y\subseteq N_{ϵ}(X)\}$

ただし、テンプレート:Math

テンプレート:Math （ただし、テンプレート:Math は テンプレート:Math の閉包 ）なので、空でない閉集合全体は擬距離 テンプレート:Math に関する同値類の完全代表系をなす。 更に、テンプレート:Math、テンプレート:Math が有界集合なら明らかに テンプレート:Math は有限である。以上から テンプレート:Math は テンプレート:Math 上の空でない有界閉集合全体 ${ℬ}^{\times }(M)$ 上の距離となる。

自然な埋め込み $\iota :(M,d)\to ({ℬ}^{\times }(M),d_{\mathrm{H}})$ を テンプレート:Math と定義すると、テンプレート:Math は等長埋め込みになっていて、その像は閉集合。

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

性質

以下距離空間 テンプレート:Math を固定。

• テンプレート:Math 、テンプレート:Math のとき テンプレート:Math。
• テンプレート:Math のとき テンプレート:Math （ただし、テンプレート:Math は テンプレート:Math の直径）。
• テンプレート:Math について テンプレート:Math の内部は空でないとする。このとき テンプレート:Math と テンプレート:Math のハウスドルフ距離が十分小さければ、テンプレート:Math。
• テンプレート:Math、テンプレート:Math とする。このとき テンプレート:Math であり、テンプレート:Math は テンプレート:Math　を満たす最大のテンプレート:Math。

部分集合の空間

テンプレート:Math を距離空間、${ℬ}^{\times }(M)$ をその上の空でない有界閉集合全体、${𝒯ℬ}^{\times }(M)$ を空でない全有界閉集合全体、${𝒦}^{\times }(M)$ を空でないコンパクト部分集合全体、${𝒫}_{\mathrm{f}\mathrm{i}\mathrm{n}}^{\times }(M)$ を空でない有限集合全体とする。

• 距離空間の空でない部分集合について、全有界であることと、ハウスドルフ距離の意味で有限集合の極限になることが同値（つまり $\overline{{𝒫}_{\mathrm{f}\mathrm{i}\mathrm{n}}^{\times }(M)}={𝒯ℬ}^{\times }(M)$）。
• 上からも明らかなように空でない全有界集合のハウスドルフ距離の意味での極限は全有界（つまり ${𝒯ℬ}^{\times }(M)$ は閉）。
• テンプレート:Math が完備なら ${ℬ}^{\times }(M)$ も完備（テンプレート:Math は ${ℬ}^{\times }(M)$ の閉部分集合と見なせるので逆も真）。
• ${𝒦}^{\times }(M)$ 上のハウスドルフ距離から入る距離位相はヴィートリス位相と一致する。

以下 テンプレート:Math は完備距離空間とする。

距離の性質のハウスドルフ距離への遺伝

空間＼性質	有界	固有	コンパクト	可分	弧長	測地	固有かつ測地
${ℬ}^{\times }(M)$	◯	◯	◯	×	◯	×	◯
${𝒦}^{\times }(M)$	◯	◯	◯	◯	×	×	◯

類似物

変換群による変形

テンプレート:Math を距離空間、テンプレート:Math を部分集合 テンプレート:Math を テンプレート:Math の等長変換（の一部）からなる群とする。このとき

$d_{\mathrm{H},G}(X,Y):=\underset{\gamma \in G}{\inf }\{d_{\mathrm{H}}(X,\gamma (Y))\}$

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

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

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

応用

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

関連項目

• グロモフ・ハウスドルフ収束
• テンプレート:仮リンク
• テンプレート:仮リンク
• 連続体 (位相空間論)
• テンプレート:仮リンク
• ワッサースタイン計量
• レヴィ–プロホロフ計量