ハウスドルフ距離のソースを表示

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

== 定義 ==
[[ファイル:Hausdorff_distance_sample.svg|thumb|Components of the calculation of the Hausdorff distance between the green line X and the blue line Y.]]
距離空間 {{math|(''M'' ,''d'' )}} の空でない<ref group="注釈">空集合にも定義できるが空集合は孤立点となり、集合族が良い性質を満たさなくなる。</ref>[[部分集合]]全体 <math>\mathcal{P}^\times(M)</math> 上の[[距離函数#一般化|拡張擬距離]] <math>d_{\rm H} : \mathcal{P}^\times(M)\times\mathcal{P}^\times(M) \rightarrow \mathbb{R}_{\ge 0}\cup\{\infty\}</math> を
:<math>d_{\rm H}(X,Y) := \rm{max}\{\sup_{x\in X}d(x,Y) , \sup_{y\in Y}d(y,X)\}</math> 
と定義する（ただし、{{math|''X''}}、{{math|''Y''}} は距離空間 {{math|(''M'' , ''d'' ))}} の任意の空でない部分集合で、<math>d(x,Y) := \inf_{y\in Y}d(x,y)</math> ）。{{math|''d''<sub>H</sub>}} をハウスドルフ距離という<ref name="BH">Martin R.Bridson and André Haefliger, ''Metric Spaces of Non-positive Curvature'',Springer,1999,p70-71</ref>。

これは次のように表現することも出来る。
:<math>d_{\rm H}(X,Y) = \inf\{\epsilon > 0 : X\subseteq N_\epsilon(Y),Y\subseteq N_\epsilon(X)\}</math> 
ただし、{{math|''N''<sub>&epsilon;</sub>(''X'' ) &#58;&#61; {''p'' &isin;''M'' : d(p,X) < &epsilon;} }}

{{math|''d''<sub>H</sub>(''X'' ,''Y'' ) &#61; 0 &hArr; cl<sub>''M''</sub>(''X'' ) &#61; cl<sub>''M''</sub>(''Y'' )}} （ただし、{{math|cl<sub>''M''</sub>(''X'' )}} は {{math|''X''}} の[[閉包 (位相空間論)|閉包]] ）なので、空でない[[閉集合]]全体は擬距離 {{math|''d''<sub>H</sub>}} に関する[[同値類]]の[[同値関係#商集合|完全代表系]]をなす。
更に、{{math|''X''}}、{{math|''Y''}} が[[有界集合]]なら明らかに  {{math|''d''<sub>H</sub>(''X'' ,''Y'' )}} は有限である。以上から {{math|''d''<sub>H</sub>}} は {{math|''M''}} 上の空でない有界閉集合全体 <math>\mathcal{B}^\times(M)</math> 上の距離となる。

自然な埋め込み <math>\iota : (M,d)\rightarrow (\mathcal{B}^\times(M),d_{\rm H})</math> を {{math|''&iota;''(''x'') &#58;&#61; {x} }} と定義すると、{{math|''&iota;''}} は等長埋め込みになっていて、その像は閉集合。

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

== 性質 ==
以下距離空間 {{math|''M''}} を固定。
*{{math|''p'' &isin;''M''}} 、{{math|''X'' , ''Y'' &sube;''M''}} のとき {{math|''d'' (''p'', ''Y'' ) &le; ''d'' (''p'', ''X'' ) + ''d''<sub>H</sub>(''X'' ,''Y'' )}}。
*{{math|''X'' , ''Y'' &sube;''M''}} のとき {{math|dia(''Y'' ) &le; dia(''X'' ) + 2&middot;''d''<sub>H</sub>(''X'' ,''Y'' )}} （ただし、{{math|dia(''X'' )}} は {{math|''X''}} の[[径|直径]]）。
*{{math|''X'' , ''Y'' &sube;''M''}} について {{math|''X'' &cap;''Y''}} の[[内部 (位相空間論)|内部]]は空でないとする。このとき {{math|''Z'' &sube; ''M''}} と {{math|''X''}} のハウスドルフ距離が十分小さければ、{{math|''Z'' &cap;''Y'' &ne; &empty;}}。
*{{math|''X'' , ''Y'' , ''Z'' &sube;''M''}}、{{math|''d''<sub>H</sub>(''X'' ,''Z'' ) &le; ''a'' , ''d''<sub>H</sub>(''Z'' ,''Y'' ) &le; b}} とする。このとき {{math|''Z'' &sube; (&#8898;<sub>''r'' > ''a''</sub> ''N''<sub>''r''</sub> (''X'' ))&cap;(&#8898;<sub>''r'' > ''b''</sub> ''N''<sub>''r''</sub> (''Y'' ))}} であり、{{math|(&#8898;<sub>''r'' > ''a''</sub> ''N''<sub>''r''</sub> (''X'' ))&cap;(&#8898;<sub>''r'' > ''b''</sub> ''N''<sub>''r''</sub> (''Y'' ))}} は {{math|''d''<sub>H</sub>(''X'' ,''W'' ) &le; ''a'' , ''d''<sub>H</sub>(''W'' ,''Y'' ) &le; ''b''}}　を満たす最大の{{math|''W''}}。

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

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

以下 {{math|''M''}} は完備距離空間とする<ref group="注釈">このとき <math>\mathcal{K}^\times(M)=\mathcal{TB}^\times(M)</math></ref>。

{| class="wikitable" style="text-align:center"
|+ 距離の性質のハウスドルフ距離への遺伝
! 空間＼性質 !! 有界 !! [[固有距離空間|固有]] !!コンパクト!! [[可分空間|可分]] !! [[弧長距離空間|弧長]] !! [[測地距離空間|測地]] !!固有かつ測地  
|-
! <math>\mathcal{B}^\times(M)</math>
| ◯ || ◯ || ◯ || × || ◯ || × || ◯ 
|-
! <math>\mathcal{K}^\times(M)</math>
| ◯ || ◯ || ◯ || ◯ || × || × || ◯ 
|}

== 類似物 ==
;変換群による変形
{{math|''M''}} を距離空間、{{math|''X'' ,''Y'' &sube; ''M''}} を部分集合 {{math|''G'' &sube;Iso(''M'' )}} を {{math|''M''}} の[[等長写像|等長]][[変換群|変換]]（の一部）からなる[[群 (数学)|群]]とする。このとき
:<math>d_{{\rm H},G}(X,Y) := \inf_{\gamma\in G}\{d_{\rm H}(X,\gamma(Y))\}</math> 
は新たな（拡張擬）距離を定める。
空間内で位置や向きを調整してハウスドルフ距離を出来るだけ小さくした場合の極限がこれに当たる。これは下記のグロモフ・ハウスドルフ距離と元のハウスドルフ距離の中間的なものである。
;グロモフ・ハウスドルフ距離
{{Main|グロモフ・ハウスドルフ収束}}
上の場合は固定した空間内で位置や向きを調整したが背景となる空間そのものを取り替えることで、2つの図形の形状の差のみを取り出したものがグロモフ・ハウスドルフ距離である。

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

== 注釈 ==
<references group="注釈"/>

== 出典 ==
<references />

== 関連項目 ==
*[[グロモフ・ハウスドルフ収束]]
*{{仮リンク|フレシェ距離|en|Fréchet distance}}
*{{仮リンク|半連続性|en|HemicontinuityJoan Gaspart}}
*[[連続体 (位相空間論)]]
*{{仮リンク|シェイプ理論|en|Shape theory (mathematics)}}
*[[ワッサースタイン計量]]
*[[レヴィ–プロホロフ計量]]

{{Normdaten}}
{{DEFAULTSORT:はうすどるふきより}}
[[Category:位相幾何学]]
[[Category:距離空間]]
[[Category:幾何学的トポロジー]]
[[Category:計量幾何学]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]