マンハッタン距離

質問

http://oshiete1.goo.ne.jp/kotaeru.php3?q=93778に絡んだ質問です。

> 一般の集合Ｘの距離と言うのは、a,b∈Ｘを引数とする実数値２変数関数で
> (1) d(a,b)≧0 、a=b ⇔ d(a,b)＝0
> (2) d(a,b)= d(b,a)
> (3) d(a,b)+ d(b,c)≧d(a,c) （三角不等式と言います）
> の３つの条件を満たすものです。

> ユークリッド空間の２点x=(x_1,x_2,…,x_n)と y=( y_1,y_2,…,y_n) の距離は通常
> |x-y|= sqrt((x_1 - y_1)^2 + (x_2 - y_2)^2 + … + ( x_n- y_n)^2 )
> で定義されます（これをユークリッド距離と言います）が、これだけがユークリッド空間
> の距離の唯一の定義というわけではありません。
> max{|x_1 - y_1|,|x_2 - y_2|,…,| x_n- y_n|}
> も距離になります。（これは通称マンハッタン距離と呼ばます。）

についてですが、マンハッタン距離が条件(3)を満たす理由がわかりません。
証明をお願いします。

回答No.1

oodaiko · ベストアンサー

単に普通の絶対値に関する三角不等式を応用するだけです。
x=(x_1,…,x_n),y=(y_1,…,y_n),z=(z_1,…,z_n)とし、マンハッタン距離を
d(*,*)とすると

d(x,z)＝ max{|x_1-z_1|,…,|x_n-z_n|}
≦ max{|x_1-y_1|+|y_1-z_1| ,…,|x_n-y_n|+|y_n-z_n| }
≦ max{|x_1-y_1|,…,|x_n-y_n|} + max{|y_1-z_1| ,…,|y_n-z_n| }
=d(x,y)+d(y,z)

最初の不等号は、三角不等式により右辺の max をとる集合の要素がそれに対応する
左辺のものよりすべて大きいから。

次の不等号は
max{|x_1-y_1|+|y_1-z_1| ,…,|x_n-y_n|+|y_n-z_n| }＝|x_i-y_i|+|y_i-z_i|
とすれば
|x_i-y_i|≦ max{|x_1-y_1|,…,|x_n-y_n|}
|y_i-z_i|≦max{|y_1-z_1| ,…,|y_n-z_n| }
だから

お礼

二つ目の不等式の所で躓いていました。
ありがとうございました。