Manhattan Distance Memo

TL;DR

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

マンハッタン距離

ある二点i,ji, jのマンハッタン距離は以下のように表される。 xixj+yiyj|x_i - x_j| + |y_i - y_j|

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

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

そこで、45度回転させるという手法を使う。45度回転というのは(x,y)>(xy,x+y)(x', y') -> (x - y, x + y)となる変換のこと。本来は2\sqrt{2}が大きさとしてかかるが、大きさが本質でない場合は無視できる。つまり、x+y,xyx+y, x-yなどが見えたら45度回転の可能性を疑うとよい...らしい。

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

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

x=max(x,x)|x| = max(x, -x)

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

xixj+yiyj=max(xixj,xi+xj)+max(yiyj,yi+yj)=max((xixj)+(yiyj),(xixj)+(yiyj),(xixj)(yiyj),(xixj)+(yiyj))=max((xi+yi)(xj+yj),(xiyi)+(xjyj),(xiyi)(xjyj),(xi+yi)+(xj+yj))|x_i - x_j| + |y_i - y_j| = max(x_i - x_j, -x_i + x_j) + max(y_i - y_j, -y_i + y_j) \\ = max((x_i - x_j) + (y_i - y_j), -(x_i - x_j) + (y_i - y_j), (x_i - x_j) - (y_i - y_j), -(x_i - x_j) + (y_i - y_j)) \\ = max((x_i + y_i) - (x_j + y_j), -(x_i - y_i) + (x_j - y_j), (x_i - y_i) - (x_j - y_j), -(x_i + y_i) + (x_j + y_j))

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

max((xi+yi)(xj+yj),(xiyi)(xjyj))max((|x_i + y_i) - (x_j + y_j)|, |(x_i - y_i) - (x_j - y_j)|)

と表すことができるので、x+y,xyx + y, x - yが出てくるので、x=x+y,y=xyx' = x + y, y' = x - yと置くことができるようになってくる。

なので

dij=max(xixj,yiyj)d_{ij} = max(|x_i' - x_j'|, |y_i' - y_j'|)

と表すことができる。

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

max1in,1jn(dij)max_{1\leq i\leq n,1\leq j \leq n}(d_{ij})

これを変形すると

max1in,1jn(max(xixj,yiyj))max_{1\leq i\leq n,1\leq j \leq n}(max(|x_i' - x_j'|, |y_i' - y_j'|))

になって、最初のmax1in,1jnmax_{1\leq i\leq n,1\leq j \leq n}と二回目のmaxmaxは入れ替えても結果が変わらない。

max(max1in,1jn(xixj,yiyj))max(max_{1\leq i\leq n,1\leq j \leq n}(|x_i' - x_j'|, |y_i' - y_j'|))

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

max1in,1jn(xixj)=max1in(xi)min1jn(xj)max_{1\leq i\leq n,1\leq j \leq n}(|x_i' - x_j'|) = max_{1\leq i \leq n}(x_i') - min_{1\leq j \leq n}(x'_j)

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

max(max1in(xi)min1jn(xj),max1in(yi)min1jn(yj))max(max_{1\leq i \leq n}(x_i') - min_{1\leq j \leq n}(x'_j), max_{1\leq i \leq n}(y_i') - min_{1\leq j \leq n}(y'_j))

こうするとx+y,xyx+y, x-yのそれぞれの最大、最小を求めることはO(m)O(m)なので、解くことができる。

ちなみに高次元空間に拡大するとRkR^kのとき、(O(k2km))(O(k2^km))らしい。むずかしいね。

この記事に関するIssueをGithubで作成する

Read Next