大人になってからの再学習

ハウスドルフ距離 (Hausdorff distance)

数学

ネット上を検索しても、あまり情報が見つからなかったので簡単なまとめ。

ハウスドルフ距離とは、2点間の距離ではなく、2つの「集合」の間の距離を表すもの。

英語版Wikipediaでは次の式で表現されている。

sup, infを知らないとパッと見ただけでは分かりにくいけど、次のように表現されることもある。
こちらの方がわかりやすいかも。

$h(A, B) = \max_{a \in A} \{ \min_{b \in B} \{ d(a, b)\}\}$
http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html

それでもわかりにくい場合のために、直観的な説明をしてみる。

「集合Aのどの点であっても、少なくとも距離dHだけ進めば集合Bのどれかの点に到達できる。」
同じく
「集合Bのどの点であっても、少なくとも距離dHだけ進めば集合Aのどれかの点に到達できる。」
このような距離dHをハウスドルフ距離と言う。

これはつまり、「集合Aに含まれる点から集合Bまでの最短距離を求めたもののうちの、最大値」ということになる。

このような距離の表し方は、幾何学の分野で用いられることも多く、例えば2つの多角形の類似度を表すために用いられたりもする。
Wikipediaでの説明では理解しにくい、Wolfram MathWorldの説明では簡潔すぎると感じる場合、次のページでは、図やアニメーションで概念をわかりやすく説明していて、視覚的に理解できる。

■ Hausdorff distance between convex polygons
http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html

上記ページに含まれるステップバイステップでの説明は次の通り。

↑点群A、点群B間のハウスドルフ距離 h(A,B)をこれから求める。

↑点a1と、点群Bに含まれる各点b1,b2,b3との距離を求める。

↑最も短いものを記憶しておく。

↑点a2と、点群Bに含まれる各点b1,b2,b3との距離を求める。

↑最も短いものを記憶しておく。

↑最後に、記憶していた距離から、最も値の大きなものを求める。

↑これが、点群A、点群B間のハウスドルフ距離 h(A,B)である。

↑点群Aのどの点からでも、距離 h(A,B) = d(a1, b1) 以内で、点群Bのいずれかの点に到達できる。

また、上記と同じWebページには、自分で作図した2つの多角形間のハウスドルフ距離を算出する様子を見ることができるアプレットも公開されている。