「領域探索」の版間の差分
ナビゲーションに移動
検索に移動
細 ("領域探索" を保護しました。 [edit=sysop:move=sysop]) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
2次元の場合, 平面上の与えられた<math>n\,</math>点の集合<math>S\,</math>に対して, 質問多角形<math>Q\,</math>が与えられたとき, <math>Q\,</math>に含まれる<math>S\,</math>の点を列挙する問題. %点位置決定問題と同様に地理情報データベースなどで基本的な問題としてしばしば生じる. 高次元の問題も同様に定義される. 質問に高速に応えるため, 通常は前処理が施され, アルゴリズムの性能は, 前処理時間, 記憶領域, 応答時間の3点を総合して評価される. 区間木, 領域木などの木構造のデータ構造を用いた方法やバケット法などが有名である. | 2次元の場合, 平面上の与えられた<math>n\,</math>点の集合<math>S\,</math>に対して, 質問多角形<math>Q\,</math>が与えられたとき, <math>Q\,</math>に含まれる<math>S\,</math>の点を列挙する問題. %点位置決定問題と同様に地理情報データベースなどで基本的な問題としてしばしば生じる. 高次元の問題も同様に定義される. 質問に高速に応えるため, 通常は前処理が施され, アルゴリズムの性能は, 前処理時間, 記憶領域, 応答時間の3点を総合して評価される. 区間木, 領域木などの木構造のデータ構造を用いた方法やバケット法などが有名である. | ||
| + | |||
| + | [[Category:計算幾何|りょういきたんさく]] | ||
2008年11月14日 (金) 09:39時点における最新版
【りょういきたんさく (range search)】
2次元の場合, 平面上の与えられた点の集合に対して, 質問多角形が与えられたとき, に含まれるの点を列挙する問題. %点位置決定問題と同様に地理情報データベースなどで基本的な問題としてしばしば生じる. 高次元の問題も同様に定義される. 質問に高速に応えるため, 通常は前処理が施され, アルゴリズムの性能は, 前処理時間, 記憶領域, 応答時間の3点を総合して評価される. 区間木, 領域木などの木構造のデータ構造を用いた方法やバケット法などが有名である.
