マンハッタン距離は45°回転
2次元平面上のマンハッタン距離は、2点$ A(x_A, y_A), $ B(x_B, y_B)について
$ d_{AB} = |x_A - x_B| + |y_A - y_B| で与えられる。
このとき、$ x_A, x_B, $ y_A, y_B間の大小関係によって上式は
$ d_{AB} = max(x_A - x_B + y_A - y_B, -(x_A - x_B) + y_A - y_B, x_A - x_B - (y_A - y_B), -(x_A - x_B) -(y_A - y_B))
$ d_{AB} = max(x_A + y_A -(x_B + y_B), -(x_A - y_A) - -(x_B - y_B), x_A - y_A -(x_B - y_B), -(x_A + y_A) - -(x_B + y_B))
$ x' = x - y,\quad y' = x + yとして、
$ d_{AB} = max(y'_A - y'_B, -(x'_A - x'_B), x'_A - x'_B, -(y'_A - y'_B))
$ d_{AB} = max(|x'_A - x'_B|, |y'_A - y'_B|)
$ A, Bを$ A'(x_A - y_A, x_A + y_A), $ B'(x_B - y_B, x_B + y_B)と変換すると、変換後の座標系では軸を分離して考えることができる。
リファレンス
例題