https://ir5.hatenadiary.org/entry/20090928/1254203385

問題

$R^k$ 空間に $n$ 個の点がある． $n$ 点から2つの点を選び，2点間のマンハッタン距離を最大化したい．
ただし，マンハッタン距離 $||\cdot ||_{1}$ とは，2点 $x,y\in R^k$ に対して
$||x-y||_{1} = \sum_{i=1}^{k}|x_i-y_i|$
で与えられる距離のことである．

単純に全通り試すと $O(kn^2)$ だけの計算量がかかるが， $n$ が大きいと計算コストがかなり大きくなる．
そこで， $n$ に比例する計算量のアルゴリズムが知りたい．どうすればよいか．

制約条件

$2^k$ は $n$ に比べてとても小さい．(具体的には $n \le 100000, k \le 6$ くらい．)

解法

Step 1

まず， $||\cdot ||_{\infty}$ という距離を導入しておく．
これは，
$||x||_{\infty} = \max\{ x_i ; 1\le i\le k \}$ …(1)
で定義される．

Step 2

マンハッタン距離は，定義より次のようにも表すことが出来る．
[tex:||x||_{1} = \max\{ ; y \in \{-1,+1\}^k \}]…(2)
ここで，[tex:]は通常のユークリッド空間における内積([tex:={x_1}{y_1}+...+{x_k}{y_k}])， $\{-1,+1\}^k$ は $k$ 次ベクトルのうち各成分が-1か+1であるものの全体で， $2^k$ 個の $k$ 次ベクトルからなる．

ここで， $k'=2^k$ とし，また写像 $f:R^k \rightarrow R^{k'}$ を
[tex:f(x) = \{ ; y \in \{-1,+1\}^k \}]…(3)
とおく．*1
すると，(1)式を用いると，(2)はさらに
$||x||_{1} = ||f(x)||_{\infty}$ …(4)
と記すことができる．

Step 3

問題は， $||x-y||_{1}$ が最大となるような点 $x,y$ の組を $n$ に比例する計算量で探すことであった．
(3)の定義よりfには線型性が成り立つ( $f(z-z')=f(z)-f(z')$ )から，(4)より
$||x-y||_{1} = ||f(x-y)||_{\infty} = ||f(x)-f(y)||_{\infty}$ …(5)
となる．
(5)より，問題は $R^k'$ 空間上にて点 $\{ f(x) \}$ の $||\cdot ||_{\infty}$ 距離を最大化する問題に帰結できる．

$\{ f(x) \}$ を求めるには $O(nk2^k)$ の計算量がかかる．

Step 4

$||\cdot ||_{\infty}$ 距離を最大化するのは簡単である．実際， $S=\{ f(x) \}$ とすると
$\begin{eqnarray} \max_{x',y' \in S} ||x'-y'||_{\infty} &=& \max_{x',y' \in S} \max_{1 \le i \le k'} |x'_i - y'_i| \\ &=& \max_{1 \le i \le k'} \max_{x',y' \in S} |x'_i - y'_i| \end{eqnarray}$ …(6)
となる． $\max_{x',y' \in S} |x'_i - y'_i|$ は $i$ 番目の座標軸の中で最大のものから最小のものを引いたものに等しく，これは $O(n)$ で求められる．
そこで，(6)式は $O(k'n)=O(n2^k)$ で求めることが出来る．

計算量

上のStep 3, Step 4より，全体では $O(nk2^k)$ の計算量がかかる．
$k$ が少しでも大きくなるとこのアルゴリズムは使えなくなることに注意．

参考文献

15-859(J) Metric Embeddings, Fall 2003 Lecture Notes, Sep 2

*1:yの元はk'個あるのでこれらを単純に並べることでk'次ベクトルを作れる．