2015/05/26

L1距離(マンハッタン距離)の意味と性質

分野: 座標,ベクトル  レベル: 最難関大学

座標平面上の二点 $A(a_1,a_2),B(b_1,b_2)$ の間の距離を
$d(A,B)=|a_1-b_1|+|a_2-b_2|$
で測ったものを $L^1$ 距離(マンハッタン距離)と言う。

マンハッタン距離とユークリッド距離

・二点間の遠さを定量的に表現するのが距離です。我々が普段よく使うのは以下の $L^2$ 距離(ユークリッド距離)です:
$d(A,B)=\sqrt{(a_1-b_1)^2+(a_2-b_2)^2}$

・しかし,場合によっては $L^1$ 距離を用いたほうがよい場合があります。例えば,座標軸に平行にしか移動できない場合,$L^1$ 距離で測るのが適切です。
実際,碁盤の目状の都市(アメリカのマンハッタン,日本だと平城京など)の二点間の最短距離は $L^1$ 距離で表現できます(マンハッタン距離と呼ばれる理由!)。

マンハッタン距離

$A(2,3)$ と $B(5,7)$ の距離は,

  • ユークリッド距離だと $\sqrt{3^2+4^2}=5$
  • マンハッタン距離だと$(5-2)+(7-3)=7$

(平城京で二条三坊から五条七坊に移動するには最低7ブロックの移動が必要)

当然ですが,ユークリッド距離よりもマンハッタン距離の方が長くなっています。

$L^1$ 距離の性質など

・ $L^1$ 距離は一般の「距離」が満たすべき性質(距離の公理)を満たしています(証明は練習問題にどうぞ):
1. $d(A,B)\geq 0$  また,$d(A,B)=0\iff A=B$
2. $d(A,B)=d(B,A)$
3. $d(A,B)+d(B,C)\geq d(A,C)$(三角不等式)

l1距離の単位球

・原点から $L^1$ 距離が $1$ であるような点の集合(単位球)は図のような正方形になります。

・三次元以上の空間においても,$L^1$ 距離は同様に定義できます:
$d(A,B)=\displaystyle\sum_{i=1}^n|a_i-b_i|$

東大の入試問題

$L^1$ 距離にまつわる東大の問題を紹介します。
1994年東大理系第6問の(1)です。(文言は少し変えています)

問題

$d(O,A)$ は $O$ と $A$ の $L^1$ 距離とする。原点 $O$ と $A(1,1)$ に対し,$d(O,P)=d(P,A)$ を満たす点 $P(x,y)$ の範囲を$(x,y)$ 平面上に図示せよ。

解答

$|x|+|y|=|x-1|+|y-1|$ を満たす点の集合を図示せよ,という問題。愚直にやると,絶対値を外すために場合分けが $3\times 3=9$ 通り必要だが,対称性を考えると以下の四通りだけ調べればよいことが分かる。

L1距離にまつわる東大の問題
  • $x\geq 1,y\geq 1$ の場合,$x+y=x-1+y-1$ を満たす点は存在しない。
  • $0 <x <1,y\geq 1$ の場合,$x+y=1-x+y-1\\\iff x=0$

となり不適。

  • $x\leq 0, y\geq 1$ の場合,$-x+y=1-x+y-1$ は常に成立。
  • $0 <x <1,0 <y <1$ の場合,$x+y=1-x+1-y\\\iff x+y=1$

以上より,答えは図の青い領域(境界含む)。

「垂直二等分線」が二次元の広がりを持つというのは驚きですね。

急いでいるときに「直線で進んだら $\frac{\sqrt{2}}{2}$ 倍に時短できるのに!」と思うことありますよね。

Tag: 東大入試数学の良問と背景知識まとめ

分野: 座標,ベクトル  レベル: 最難関大学