マンハッタン距離が最大である2点を選ぶ問題

問題

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^knに比べてとても小さい.(具体的には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\}^kk次ベクトルのうち各成分が-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'次ベクトルを作れる.