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

10.5

 最近傍法

■

325

図10-5　R 木の例

根は木のすべての長方形を含む最小の長方形領域

(x

low

, y

low

, x

high

, y

high

)

を表す。

内部節点には、同様に、子孫節点のすべての長方形を含む最小の長方形領域が付随

する。

R

木

における実際の長方形は、葉にのみ格納される。根を除いて、すべての

長方形領域（内部節点や葉に付随するかどうかにかかわらず）は、親節点の領域に完

全に含まれる。

これらの空間構造を用いて本章の冒頭で示した問題の解法を示す。

10.5

 最近傍法

2

次元点集合

P

が与えられ、

P

のどの点が、ターゲットクエリ点

x

に最も近いかを

決定するよう求められたとする。

k-d

木を使って、どのようにこのクエリに効率的

に回答するかを示す。木がうまく点を分割したと仮定すると、再帰的に木を走査す

るたびに、木の約半分の点を棄却できる。通常の点の分布の

k-d

木では、レベル

i

の

節点はレベル

i

＋

1

の長方形のほぼ

2

倍の長方形を表す。この性質によって、最近傍

（

Nearest Neighbor

）アルゴリズムは

O(log n)

の性能となる。最近点の候補になる

には離れすぎている点を含む部分木全体を棄却できるからだ。しかし、この再帰は、

次に示すように、通常の二分木探索よりも少しばかり複雑である。

図10-6に示すように、（黒い四角の）ターゲット点がもし挿入されたとしたら、点

9

の節点の子になるだろう。そこで、後に示すアルゴリズムにある

nearest

関数を

この点に対して実行すると、まず、点

1

との鉛直線距離 ...