凸多角形の場合、はの頂点からの任意の点までd(A, B)
の距離の最大値です。したがって、任意の点から凸多角形までの距離を計算できれば、ハウスドルフ距離を計算するのはそれほど難しくありません。A
B
ポイントから凸多角形までの距離を計算するには、最初にポイントがポリゴンの内側にあるかどうかをテストする必要があります(その場合、距離は0です)。次に、境界線セグメントのいずれかまでの最小距離が見つからない場合。
他の質問に対する答えはノーです。例として、AとBの両方を原点を中心とする同じ2x2の正方形とします。Aを4つの1x1の正方形に分割します。各AiからBまでのハウスドルフ距離はですsqrt(2)
が、AからBまでの距離は0です。
更新:頂点に関する主張はすぐには明らかではないため、有限数の次元で適切な証明をスケッチします。私が証明しようとしている結果はd(A, B)
、ポリゴンと凸面の両方で計算する場合、の頂点からB
の距離を見つけるだけで十分であるということです。(の最も近いポイントは頂点ではない可能性がありますが、の最も遠いポイントの1つは頂点である必要があります。)A
B
B
A
どちらも有限の閉じた形状であるため、コンパクトです。コンパクトさから、そこから可能な限り離れた点p
が存在しなければなりません。コンパクトさから、可能な限りに近い点が存在しなければなりません。A
B
q
B
A
この距離は、A
とB
が同じポリゴンである場合にのみ0になります。この場合、の頂点でその距離を達成することは明らかですA
。したがって、一般性を失うことなく、からp
への距離が正であると想定できq
ます。
q
からの線に垂直な平面(高次元では、ある種の超平面)に接するように描画p
しq
ます。B
この平面を横切る点はありますか?たとえば、1つある場合は、からまでr
の線分のすべての点が凸であるため、中にある必要があります。しかし、この線分には、の定義と矛盾する、より近い点が存在する必要があることを示すのは簡単です。したがって、この平面を横切ることはできません。q
r
B
B
p
q
q
B
明らかp
に内部の点になることはできません。内部の点である場合は、からの光線に沿って続行q
すると、背後にある境界の平面から遠く離れたp
点が見つかり、の定義と矛盾します。がの頂点である場合、結果は自明に真になります。したがって、唯一の興味深いケースは、が頂点の境界上にあるが頂点ではない場合です。A
B
p
p
A
p
A
もしそうなら、それからp
表面にあります。そのサーフェスが作成した平面と平行でない場合、背後にある平面から離れて、そのサーフェスに沿って移動し、よりもB
遠くにあるポイントを見つけるのは簡単です。したがって、その表面はその平面に平行でなければなりません。は有限であるため、そのサーフェスはどこかの頂点で終了する必要があります。これらの頂点は、その平面からと同じ距離にあるため、少なくとも。と同じ距離にあります。したがって、から可能な限り離れた頂点が少なくとも1つ存在します。B
p
A
p
B
p
A
B
そのため、ポリゴンの頂点から他のポリゴンまでの距離の最大値を見つけるだけで十分でした。
q
(読者にとって楽しい演習として、頂点のないポリゴンのペアを作成することはお任せします。)