アルゴリズムクイックリファレンス 第2版

328

■

10

章 空間木構造

10.5.2

 文脈

この方式を、クエリ点

x

と

p

∈

P

の各点との距離をそれぞれ計算する力任せ方式

と比較するときには、次の

2

つの重要なコストを考慮しなければならない。

(1)k-d

木構築のコスト、

(2)

木構造の中でクエリ点

x

を見つけるコストである。これらのコ

ストとのトレードオフは、次のようになる。

次元の数

次元数が増大すると、

k-d

木構築のコストは、その有用性を圧倒する。

20

次元を超えると、全点を直接比較する方式よりも効率が落ちると信じ

ている専門家もいる。

入力集合の点の数

点の個数が少ないと、構造構築コストが性能向上を上回る可能性がある。

二分木は、木への節点を追加削除しても平衡を保てるため、効率的な探索構造を

保つことができる。残念ながら

k-d

木では表現する次元平面の構造情報が複雑なた

めに、簡単に平衡をとれない。理想解は、

(a)

葉の節点が木の同じレベルにあるか、

あるいは

(b)

すべての葉がすべての他の葉から

1

レベル以内にあるような

k-d

木を最

初に構築することだ。

10.5.3

 解

k-d

木があるとして、

最近傍法

は例10-1のように実装される。

例

10-1

 

k-d

木による最近傍クエリの実装（

KDTree

のメソッド）

public IMultiPoint nearest (IMultiPoint target) {

if (root == null) return null;

//

対象が挿入されるとしたら、親になるであろう節点を見つける。

//

これは、最近点の最良の候補となる。 ...