チェビシェフ距離への置き換えを利用して（k次元）マンハッタン距離の最大値を求める方法

LeetCode Weekly Contest 146のQ4でN個の点の3次元マンハッタン距離の最大値を求める問題が出たのでメモ。

内容的には

マンハッタン距離が最大である2点を選ぶ問題 - ICPC突破専用ザク

を理解する過程で噛み砕いたものなので、上記記事を既読の方は本稿を読むには及ばない。

MathJaxの不具合なのか、 $\max$ の下に $2^{k-1}$ が書けなかったので $2^k/2$ で代用。

2次元の場合

例題

N個の点の二次元座標が与えられ、2点 $(x_i,y_i), (x_j,y_j)$ 間のマンハッタン距離 $|x_i-x_j|+|y_i-y_j|$ を考えた時、マンハッタン距離の最大値を求めよ。

愚直にやると全てのペア（ $_NC_2$ 組ある）について距離を算出することになって計算量は $O(kN^2)$ （kは次元数=2）になり、 $2\le N\le 10^6$ のような制約だと時間内に解くことができない。

$f: (x,y) → (x-y,x+y)$ という写像を考える。

$$ \begin{align}
&ManhattanDistance( (x_i,y_i), (x_j,y_j) ) \\
&= |x_i-x_j| + |y_i-y_j| \\
&= \max(x_i-x_j, x_j-x_i) + \max(y_i-y_j, y_j-y_i) ) \\
&= \max( (x_i-x_j)+(y_i-y_j), (x_i-x_j)+(y_j-y_i), (x_j-x_i)+(y_i-y_j), (x_j-x_i)+(y_j-y_i) ) ) \\
&= \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) ) ) \\
&= \max( \max( (x_i-y_i)-(x_j-y_j), (-x_i+y_i)-(-x_j+y_j) ), \max( (x_i+y_i)-(x_j+y_j), (-x_i-y_i)-(-x_j-y_j) ) ) \\
&= \max( |(x_i-y_i)-(x_j-y_j)|, |(x_i+y_i)-(x_j+y_j)| ) \\
&= ChebyshevDistance( (x_j-y_j, x_j-y_j), (x_i+y_i, x_i+y_i) ) \\
&= ChebyshevDistance( f(x_i,y_i), f(x_j,y_j) )
\end{align} $$

ここで

チェビシェフ距離（Chebyshev distance; $L_\infty$ 距離）
= 各座標の差（の絶対値）の最大値を2点間の距離とする
チェビシェフ距離 - Wikipedia

$f(x_i,y_i)$ の各成分を

$f(x_i,y_i)_0 = x_i - y_i$
$f(x_i,y_i)_1 = x_i + y_i$

と表すとして

$$ \begin{align}
&\max_{i,j\in N,i\neq j} ManhattanDistance( (x_i,y_i), (x_j,y_j) ) \\
&= \max_{i,j\in N,i\neq j} ChebyshevDistance( f(x_i,y_i), f(x_j,y_j) ) \\
&= \max_{d\in{0,1}} \max_{i,j\in N,i\neq j} |f(x_i,y_i)_d - f(x_j,y_j)_d| \\
&= \max_{d\in{0,1}} ( \max_{i\in N} f(x_i,y_i)_d - \min_{i\in N} f(x_i,y_i)_d )
\end{align} $$

N個の点をfで射影した先で、各軸における最大値と最小値の差を求め、その差の（全次元の）最大値が求める答えとなる。計算量も $O(kN)$ に抑えることができた。

このfでの射影は45度の回転（※ $\sqrt2$ 倍の拡大を伴っている）に対応している。
いわゆる「マンハッタン距離は45度回転させて考える」というやつである。

3次元以上の場合

2次元の場合と同様に、 $k$ 次元空間の2点間のマンハッタン距離は $2^{k-1}$ 次元でのチェビシェフ距離に置き換えることができる。

次元空間のN個の点の座標を次元の空間に射影する写像fを考える
- - $x_0$ も正負を取ると $2^k$ 次元なのだけれど、 $x_0$ の項の負号が-になるものは $x_0$ の項の負号が+になるものの正負をひっくり返しただけのものと1:1で対応していて、最大値と最小値の差の絶対値を取る用途では同じになるので節約のため+になる方で代表させる。（ $x_0$ が負の項も入れて $2^k$ 次元にしても計算量や使用メモリ量が2倍になる以外の問題はない）
- 3次元の場合： $f:(x,y,z) → (x+y+z, x+y-z, x-y+z, x-y-z)$
このとき

$ManhattanDistance({\mathbf x}_0,{\mathbf x}_1) = ChebyshevDistance( f({\mathbf x}_0), f({\mathbf x}_1) )$
が言えることを利用する。

$k=3$ だとこんな感じ：
$$ \begin{align}
& ManhattanDistance( (x_0,y_0,z_0), (x_1,y_1,z_1) ) \\
\ \ \ \ &=|x_0-x_1|+|y_0-y_1|+|z_0-z_1| \\
&= \max (x_0-x_1,x_1-x_0) + \max (y_0-y_1,y_1-y_0) + \max (z_0-z_1,z_1-z_0) \\
&= \max ( (x_0-x_1) + (y_0-y_1) + (z_0-y_1), \\
& \ \ \ \ (x_0-x_1) + (y_0-y_1) - (z_0-y_1), \\
& \ \ \ \ (x_0-x_1) - (y_0-y_1) + (z_0-y_1), \\
& \ \ \ \ (x_0-x_1) - (y_0-y_1) - (z_0-y_1), \\
& \ \ \ \ -(x_0-x_1) + (y_0-y_1) + (z_0-y_1), \\
& \ \ \ \ -(x_0-x_1) + (y_0-y_1) - (z_0-y_1), \\
& \ \ \ \ -(x_0-x_1) - (y_0-y_1) + (z_0-y_1), \\
& \ \ \ \ -(x_0-x_1) - (y_0-y_1) - (z_0-y_1) ) \\
&= \max ( (x_0+y_0+z_0) - (x_1+y_1+z_1), \\
& \ \ \ \ (x_0+y_0-z_0) - (x_1+y_1-z_1), \\
& \ \ \ \ (x_0-y_0+z_0) - (x_1-y_1+z_1), \\
& \ \ \ \ (x_0-y_0-z_0) - (x_1-y_1-z_1), \\
& \ \ \ \ (-x_0+y_0+z_0) - (-x_1+y_1+z_1), \\
& \ \ \ \ (-x_0+y_0-z_0) - (-x_1+y_1-z_1), \\
& \ \ \ \ (-x_0-y_0+z_0) - (-x_1-y_1+z_1), \\
& \ \ \ \ (-x_0-y_0-z_0) - (-x_1-y_1-z_1) ) \\
&= \max ( \max ( (x_0+y_0+z_0) - (x_1+y_1+z_1), (-x_0-y_0-z_0) - (-x_1-y_1-z_1) ), \\
& \ \ \ \ \max ( (x_0+y_0-z_0) - (x_1+y_1-z_1), (-x_0-y_0+z_0) - (-x_1-y_1+z_1) ), \\
& \ \ \ \ \max ( (x_0-y_0+z_0) - (x_1-y_1+z_1), (-x_0+y_0-z_0) - (-x_1+y_1-z_1) ), \\
& \ \ \ \ \max ( (x_0-y_0-z_0) - (x_1-y_1-z_1), (-x_0+y_0+z_0) - (-x_1+y_1+z_1) ) ) \\
&= \max ( |(x_0+y_0+z_0) - (x_1+y_1+z_1)|, \\
& \ \ \ \ |(x_0+y_0-z_0) - (x_1+y_1-z_1)|, \\
& \ \ \ \ |(x_0-y_0+z_0) - (x_1-y_1+z_1)|, \\
& \ \ \ \ |(x_0-y_0-z_0) - (x_1-y_1-z_1)| ) \\
&= ChebyshevDistance( (x_0+y_0+z_0,...,x_0-y_0-z_0), (x_1+y_1+z_1,...,x_1-y_1-z_1) ) \\
&= ChebyshevDistance( f(x_0,y_0,z_0), f(x_1,y_1,z_1) ) \\
\end{align} $$

N個の点の全ペアについてのマンハッタン距離の最大値
= N個の点の全ペアについての $2^{k-1}$ 次元空間上でのチェビシェフ距離の最大値

$$ \begin{align}
& \max_{i,j\in N,i\neq j} ManhattanDistance({\mathbf x}_i, {\mathbf x}_j) \\
&= \max_{i,j\in N,i\neq j} ChebyshevDistance( f({\mathbf x}_i),f({\mathbf x}_j) ) \\
&= \max_{i,j\in N,i\neq j} \max_{d\in 2^k/2} |f({\mathbf x}_i)_d - f({\mathbf x}_j)_d| \\
&= \max_{d\in 2^k/2} \max_{i,j\in N,i\neq j} |f({\mathbf x}_i)_d - f({\mathbf x}_j)_d| \\
&= \max_{d\in 2^k/2} ( \max_{i\in N} f({\mathbf x}_i)_d - \min_{i\in N} f({\mathbf x}_i)_d ) \\
\end{align} $$

N個の点を $2^{k-1}$ 次元空間に射影して、 $2^{k-1}$ 次元各軸での最大値と最小値の差を求める。
それらの差の最大値が求める値である。
計算量は写像を求める部分が $O(k2^kN)$ 、最大値を求める部分が $O(2^kN)$ なので全体では $O(k2^kN)$ となる。