TL;DR
メモ。詳しくは最近の 45 度回転事情を参照してほしい。
マンハッタン距離
ある二点i,jのマンハッタン距離は以下のように表される。
∣xi−xj∣+∣yi−yj∣
マンハッタン距離の最大値
点がm個与えられたとき、その点間のマンハッタン距離の最大値を求めたい。
もし全探索すると、O(m2)かかってしまう。
そこで、45度回転させるという手法を使う。45度回転というのは(x′,y′)−>(x−y,x+y)となる変換のこと。本来は2が大きさとしてかかるが、大きさが本質でない場合は無視できる。つまり、x+y,x−yなどが見えたら45度回転の可能性を疑うとよい...らしい。
マンハッタン距離はそのままだと見えてこないが、以下のような変換を行うことでx+y,x−yが現れる。
まず、絶対値を以下のように考える。
∣x∣=max(x,−x)
こうすると、マンハッタン距離は
∣xi−xj∣+∣yi−yj∣=max(xi−xj,−xi+xj)+max(yi−yj,−yi+yj)=max((xi−xj)+(yi−yj),−(xi−xj)+(yi−yj),(xi−xj)−(yi−yj),−(xi−xj)+(yi−yj))=max((xi+yi)−(xj+yj),−(xi−yi)+(xj−yj),(xi−yi)−(xj−yj),−(xi+yi)+(xj+yj))
こうすると、1番目と4番目、2番目と3番目に注目すると、そこは絶対値に戻すことができて
max((∣xi+yi)−(xj+yj)∣,∣(xi−yi)−(xj−yj)∣)
と表すことができるので、x+y,x−yが出てくるので、x′=x+y,y′=x−yと置くことができるようになってくる。
なので
dij=max(∣xi′−xj′∣,∣yi′−yj′∣)
と表すことができる。
もともとの目的は下の式が求めたいことであった。
max1≤i≤n,1≤j≤n(dij)
これを変形すると
max1≤i≤n,1≤j≤n(max(∣xi′−xj′∣,∣yi′−yj′∣))
になって、最初のmax1≤i≤n,1≤j≤nと二回目のmaxは入れ替えても結果が変わらない。
max(max1≤i≤n,1≤j≤n(∣xi′−xj′∣,∣yi′−yj′∣))
になる。このとき、x′,y′はそれぞれ独立に計算できるので、一番大きいものから一番小さいものを引けばいい。なので、
max1≤i≤n,1≤j≤n(∣xi′−xj′∣)=max1≤i≤n(xi′)−min1≤j≤n(xj′)
と書くことができて、y′側も同様にすると
max(max1≤i≤n(xi′)−min1≤j≤n(xj′),max1≤i≤n(yi′)−min1≤j≤n(yj′))
こうするとx+y,x−yのそれぞれの最大、最小を求めることはO(m)なので、解くことができる。
ちなみに高次元空間に拡大するとRkのとき、(O(k2km))らしい。むずかしいね。
この記事に関するIssueをGithubで作成する