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

10.3

 交差クエリ

■

321

この例の場合は、ターゲット区画に点がないので、

3

つの隣接区画を調べる必要

がある。この方式は、多くの区画が実は空かもしれず、しかも、複数の隣接区画を

調べる必要がある、という理由から非効率な恐れがある。

5

章で説明したように、

二分探索木を使えば、解の中に含まれることのない点の集まりを考慮の対象から除

くことができる。本章では、空間木（

spatial tree

）というアイデアを導入し、それ

を使って、

2

次元平面上の点を分割し、探索時間の削減も行う。

P

の全点を前処理

して、効率的な構造を作る余分なコストは、クエリ計算の削減によって埋め合わせ

ることができて、最終的に

O(log n)

となる。探索回数が少ないようなら、力任せの

O(n)

で比較するのが最良となるだろう。

10.2

 範囲クエリ

ターゲットとなる特定の点を探すのではなく、

2

次元空間上に与えた四角形の範

囲内にあるすべての点を求めるような問題もある。

集合内の各点についてその四角

形に含まれるかどうか調べる力任せ方式は

O(n)

性能となる。

最近傍クエリのために開発したものと同じデータ構造が、「直交範囲（

orthogonal

range

）」と呼ばれるこの種のクエリに役立つ。こう呼ばれるのは四角形の領域クエ

リは平面の

x

軸と

y

軸に沿ったものとなるからだ。

O(n)

よりも性能の良い方式を生

み出す唯一の方法は、考慮から外す点の集まり、およびクエリ結果に含まれる点の

集まりを見つけることだ。後述する

k-d

木を使うと、再帰的な走査で