マンハッタン距離

648

はじめに

私はAtCoderなどの競技プログラミングを趣味でやっているのだが，その中の問題でマンハッタン距離に関するものが出題されることがある．（ D - Four Coloring など）
そこでマンハッタン距離について調べて，簡単にまとめることにした．

距離空間

集合 $X$ と，関数 $d : X \times X \to R^{+}$ に対し，関数 $d$ が以下を満たすとき， $(X, d)$ を距離空間という．（ただし， $R^{+} := {x \in R | x > 0}$ ）

$d (x, y) = 0 \Leftrightarrow x = y$

$x, y \in X$ に対し， $d (x, y) = d (y, x)$
$x, y, z$ に対し， $d (x, y) + d (y, z) \geq d (x, z)$

$d$ を $X$ 上の距離ともいう.

ユークリッド距離

$x_{1} = (x_{1}, y_{1})$ ， $x_{2} = (x_{2}, y_{2}) \in R^{2}$ に対し， $d (x_{1}, x_{2}) = \sqrt{(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}}$ と定めると，これは $R^{2}$ 上の距離となる．

マンハッタン距離（

L_{1}

距離）

$d : R^{2} \times R^{2} \to R$ を $d (x_{1}, x_{2}) = | x_{1} - x_{2} | + | y_{1} - y_{2} |$ をマンハッタン距離という．

距離になっていること

この $d$ が $R^{2}$ 上の距離になっていることを確認する．

$\begin{array}{rcl} d (x_{1}, x_{2}) = | x_{1} - x_{2} | + | y_{1} - y_{2} | = 0 & \Leftrightarrow & | x_{1} - x_{2} | = 0 \land | y_{1} - y_{2} | = 0 \\ \Leftrightarrow & x_{1} = x_{2} \land y_{1} = y_{2} \\ \Leftrightarrow & x_{1} = x_{2} \end{array}$

$d (x_{1}, x_{2}) = | x_{1} - x_{2} | + | y_{1} - y_{2} | = | y_{1} - y_{2} | + | x_{1} - x_{2} | = d (x_{2}, x_{1})$
$\begin{array}{rcl} d (x_{1}, x_{3}) = | x_{1} - x_{3} | + | y_{1} - y_{3} | & = & | x_{1} - x_{2} + x_{2} - x_{3} | + | y_{1} - y_{2} + y_{2} - y_{3} | \\ \leq & | x_{1} - x_{2} | + | x_{2} - x_{3} | + | y_{1} - y_{2} | + | y_{2} - y_{3} | \\ \leq & | x_{1} - x_{2} | + | y_{1} - y_{2} | + | x_{2} - x_{3} | + | y_{2} - y_{3} | \\ = & d (x_{1}, x_{2}) + d (x_{2}, x_{3}) \end{array}$

図形的解釈

そもそも，この距離がなぜマンハッタン距離と呼ばれるかというと，マンハッタンの道路が四角く（日本人的に言えば碁盤目状）になっており，この道に沿って移動するときのことを考えるからである．

マンハッタン距離

なお対角線（点線）が通常のユークリッド距離である．また，図から明らかなように，同一の点に対する（ユークリッド距離） $\leq$ （マンハッタン距離）である．

将棋盤の上を縦または横にしか動けない状態で，何マス動けば目的のマスにたどり着けるかを考えていることを想像すれば少しは身近に感じられるかもしれない．

問題名（任意）

$R^{2}$ 上の原点を $O$ ， $R^{2}$ 上のユークリッド距離を $d_{1}$ ，マンハッタン距離を $d_{2}$ とする．このとき $d_{1} (O, x_{1}) < d_{1} (O, x_{2})$ かつ $d_{2} (O, x_{1}) > d_{2} (O, x_{2})$ となるような $2$ 点 $x_{1} = (x_{1}, y_{1})$ ， $x_{2} = (x_{2}, y_{2})$ が存在するか．
（ユークリッド距離で測ると近く，マンハッタン距離で測ると遠くなるようなことがあるか）

解答例 例えば $(1, 5)$ ， $(3, 4)$ が条件を満たしている．

座標変換

$45$ 度回転という操作について調べていると，マンハッタン距離との関連について書かれている記事が目に留まる．また，そこでは $(x, y) \to (x - y, x + y)$ という座標変換について書かれている．そこでこの座標変換について考えてみることにする．
$A = (\begin{array}{rr} 1 & - 1 \\ 1 & 1 \end{array})$ とすると， $A (\begin{array}{r} x \\ y \end{array}) = (\begin{array}{r} x - y \\ x + y \end{array})$ となる．したがって，この行列 $A$ による線形変換を考える． $A = \sqrt{2} (\begin{array}{r} \cos \frac{π}{4} & - \sin \frac{π}{4} \\ \cos \frac{π}{4} & \sin \frac{π}{4} \end{array})$ と書けることから，この線形変換は $\frac{π}{4}$ 回転して， $\sqrt{2}$ 倍しているということがわかる．