駆け足で読む計算幾何学入門　第６章　幾何的探索

幾何的探索
- 幾何的探索の前に、スカラー的探索とは
  - 多数のデータがあって、該当データを探すとき、データに決まりがなければ、しみつぶしにするしかない
  - データに順序があれば、その順序を利用して探索をかける(ソートしたリストを用いた２分探索)
  - データに順序があり、該当データを探すだけでなく、データを入れたり出したりするときには、２分探索木を用いる
- 幾何的探索とは
  - 点と線分との位置関係、図形同士の関係などの場合、「順序」を扱うデータ構造(上述のリストや２分探索木)が使えず、異なる枠組みが必要である
- 領域探索問題
  - 幾何学要素の位置関係の探索問題
- 点位置決定問題
  - 与えられた点が属する領域の探索問題
領域探索のためのデータ構造
- 区分木
  - 長さNの区間を、N個の葉(長さ0の区間)を持つ、２分木として登録する。この木の頂点数は2N-1以下であり、木の高さはlogN以下であって、この作業はO(N)時間ででき、木の構成情報の格納にはO(N)領域しか使わない。このような２分木を区間木と呼ぶ
- 区間木の頂点は、さまざまな長さの区間に対応している
- 任意の区間は、区間木に登録された頂点の集合として表せる。表し方は複数あるが、構成頂点数を最小にするような表し方は一意に決まる
- 領域木
  - 区間木を作る。この区間木は２次元領域の２軸のうちの片方に対応する
  - 領域中の点を区間木に登録する。点であるが、区間木の葉以外の頂点にも登録することで２次元的扱いを実現するとともに、区間木として扱っていない方の軸における位置情報は、点を頂点登録するにあたっての順序に持たせる
- ヒープ探索木
  - 点を探索木に配置する
  - 配置にあたって、点の割付けは２軸のうちの片方の軸の座標で決める
  - 配置にあたって、ある点を探索木の頂点に割り当てたら、残りの頂点をもう片方の軸の座標によって異なる木に割り当てることまでを決める
点位置決定問題
応用