Manhattan Distance Memo

TL;DR

メモ。詳しくは最近の 45 度回転事情を参照してほしい。

マンハッタン距離

ある二点のマンハッタン距離は以下のように表される。

マンハッタン距離の最大値

点がm個与えられたとき、その点間のマンハッタン距離の最大値を求めたい。 もし全探索すると、かかってしまう。

そこで、45度回転させるという手法を使う。45度回転というのはとなる変換のこと。本来はが大きさとしてかかるが、大きさが本質でない場合は無視できる。つまり、などが見えたら45度回転の可能性を疑うとよい...らしい。

マンハッタン距離はそのままだと見えてこないが、以下のような変換を行うことでが現れる。

まず、絶対値を以下のように考える。

こうすると、マンハッタン距離は

こうすると、1番目と4番目、2番目と3番目に注目すると、そこは絶対値に戻すことができて

と表すことができるので、が出てくるので、と置くことができるようになってくる。

なので

と表すことができる。

もともとの目的は下の式が求めたいことであった。

これを変形すると

になって、最初のと二回目のは入れ替えても結果が変わらない。

になる。このとき、はそれぞれ独立に計算できるので、一番大きいものから一番小さいものを引けばいい。なので、

と書くことができて、側も同様にすると

こうするとのそれぞれの最大、最小を求めることはなので、解くことができる。

ちなみに高次元空間に拡大するとのとき、らしい。むずかしいね。