マンハッタン距離と45度回転

メモ

マンハッタン距離に対する「45度回転」という操作

$ (x, y)を$ (u, v) = (x+y, x-y)に変換することを伝統的に「45度回転」と呼ぶ。

$ (x, y)を$ (u, v)で表すと、距離が求めやすくなったりする。

なお、45度回転と呼ぶ理由は、45度回転して距離を√2倍にしたものだから。

$ (u, v)からマンハッタン距離を求める

まず、$ (x_1, y_1) と$ (x_2, y_2) のマンハッタン距離は$ |x_1 - x_2| + |y_1 - y_2|と表される。

これは絶対値の部分を$ \maxで表すことができて（そうすると変形しやすいので）、

$ |x_1 - x_2| + |y_1 - y_2| = \max(x_1 - x_2, x_2 - x_1) + \max(y_1 - y_2, y_2 - y_1)

$ \maxと$ +（Max-Plus代数）の分配法則より、

$ = \max((x_1 - x_2) + (y_1 - y_2), (x_1 - x_2) + (y_2 - y_1), (x_2 - x_1) + (y_1 - y_2), (x_2 - x_1) + (y_2 - y_1))

変数を並び替えて、

$ = \max((x_1 + y_1) - (x_2 + y_2), (x_1 - y_1) - (x_2 - y_2), -(x_1 - y_1) + (x_2 - y_2), -(x_1 + y_1) + (x_2 + y_2))

ここで、式を$ (u_1, v_1) = (x_1 + y_1, x_1 - y_1)と$ (u_2, v_2) = (x_2 + y_2, x_2 - y_2)で表すと、

$ = \max(u_1 - u_2, v_1 - v_2, v_2 - v_1, u_2 - u_1)

さらに$ \maxを絶対値に戻すと、

$ = \max(|u_1 - u_2|, |v_1 - v_2|)

このように、$ u軸と$ v軸を独立に見ることができる

問題

参考