イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。

73. マンハッタン距離は45度回転…がイマイチ納得できないので証明する

プログラミング アルゴリズム 数学

2次元座標系における点 p_1 = (x_1, y_1) と点 p_2 = (x_2, y_2) 間のマンハッタン距離 d(p_1, p_2) は、 d(p_1, p_2) = | x_1 - x_2 | + | y_1 - y_2 | と定義されます。

簡単に言うと「斜め移動はできず、縦横方向にしか動けない場合の距離」です。

 


f:id:ibako_piyo:20220220135640p:plain

マンハッタン距離

上図では、中央の緑マスからのマンハッタン距離を各マスに記しています。また、中央からマンハッタン距離が2以内のマスを黄色に塗っています。

このように、マンハッタン距離を考えると同一距離のマスはひし形状に出現することが分かります。そこで、距離を考える問題では座標系を45度回転させることで解きやすくなるというテクニックが知られています。

この45度回転は、主に F: (x, y) \rightarrow (x-y, x+y) という変換で達成されます。

 

…ここで、高校数学を覚えている人は「あれっ」となるわけです。何故なら、 F は純粋な「45度回転」ではないからです。2次元平面において、原点を中心とした \theta 回転を実現する一次変換行列は、

  \begin{pmatrix} \cos{\theta} & -\sin{\theta} \\ \sin{\theta} & \cos{\theta} \end{pmatrix}

です。

つまり、 F による変換は「45度回転に加えて、原点からのユークリッド距離を \sqrt{2} 倍にする」ものです。

 

純粋な45度回転ではないが…

…ただ、ここでは一旦疑問を置いておきます。重要なのはここからです。

 

2次元平面上で、 F: (x, y) \rightarrow (x-y, x+y) という変換を点 p_1, p_2 に適用して得られた点をそれぞれ P_1 = (X_1, Y_1), P_2 = (X_2, Y_2) とする。
点 p_1, p_2 間のマンハッタン距離 d(p_1, p_2) について、 d(p_1, p_2) = \max( | X_1 - X_2| , | Y_1 - Y_2 | ) が成立する。

 

結論を読むと非常に意外なことが書いてあります。 \max( | X_1 - X_2| , | Y_1 - Y_2 | ) にはチェビシェフ距離という名前がついています。つまり、この主張は「2次元平面上で "45度回転" と呼ばれる変換を各点に行えば、もともとの各点間のマンハッタン距離は、変換後の各点間のチェビシェフ距離と一致する」ということです。

 

「もともとのマンハッタン距離＝変換後のチェビシェフ距離」の証明

幾何的に考えるのは難しいので、式で証明します。

 

【証明】

点 p_1 = (x_1,y_1), p_2 = (x_2, y_2) に対して、変換 F: (x, y) \rightarrow (x-y, x+y) を適用した点を P_1 = (X_1, Y_1), P_2=(X_2, Y_2) とする。
X_1 = x_1 - y_1, Y_1 = x_1 + y_1, X_2 = x_2 - y_2, Y_2 = x_2 + y_2 である。

このとき、以下の4式が成立する。

\begin{eqnarray} X_1 - X_2 & = & (x_1 - y_1) - (x_2 - y_2) & = & (x_1 - x_2) + (-y_1 + y_2) \\ Y_1 - Y_2 & = & (x_1 + y_1) - (x_2 + y_2) & = & (x_1 - x_2) + (y_1 - y_2) \\ -X_1 + X_2 & = & -(x_1 - y_1) + (x_2 - y_2) & = & (-x_1 + x_2) + (y_1 - y_2) \\ -Y_1 + Y_2 & = & -(x_1 + y_1) + (x_2 + y_2) & = & (-x_1 + x_2) + (-y_1 + y_2) \end{eqnarray}

ここで、 d(p_1, p_2) = | x_1 - x_2 | + | y_1 - y_2 | である。つまり、2点間の x, y の差がそれぞれ正となるように絶対値を取った上で、和を取っている。

上記4式を見ると、もともとの2点間の x, y の差をそれぞれ取った上で、和を取っている。つまり「負 + 負」「負 + 正」「正 + 負」「正 + 正」のいずれかのパターンが重複なく存在している。よって、 d(p_1, p_2) = \max( | X_1 - X_2 |, |Y_1 - Y_2| ) が成立する。（証明終わり）

 

「45度回転」はマンハッタン距離をチェビシェフ距離に変換するのが目的

以上より、「45度回転」を行うことで変換前のマンハッタン距離と変換後のチェビシェフ距離が一致することが示せました。

つまり、これを達成するために「都合の良い変換」を考えるのが本質だったわけです。今回はユークリッド距離が対象ではないので、このような変換がちょうど良いのですね。