「点位置決定」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
| − | 【てんいちけってい (point location)】 | + | '''【てんいちけってい (point location)】''' |
2次元の場合, 与えられた平面上の<math>n\,</math>点からなる直線分の平面グラフ<math>S\,</math>に対して, 質問点<math>Q\,</math>が与えられたとき, <math>Q\,</math>を含む面(領域)を求める問題. 地理情報データベースなどで基本的な問題としてしばしば生じる. 高次元の問題も同様に定義される. 質問に高速に応えるため, 通常は前処理が施され, アルゴリズムの性能は, 前処理時間, 記憶領域, 応答時間の3点を総合して評価される. スラブ法, バケット法, 橋渡しチェイン法, 残存化スラブ法などが有名である. | 2次元の場合, 与えられた平面上の<math>n\,</math>点からなる直線分の平面グラフ<math>S\,</math>に対して, 質問点<math>Q\,</math>が与えられたとき, <math>Q\,</math>を含む面(領域)を求める問題. 地理情報データベースなどで基本的な問題としてしばしば生じる. 高次元の問題も同様に定義される. 質問に高速に応えるため, 通常は前処理が施され, アルゴリズムの性能は, 前処理時間, 記憶領域, 応答時間の3点を総合して評価される. スラブ法, バケット法, 橋渡しチェイン法, 残存化スラブ法などが有名である. | ||
| + | |||
| + | [[Category:計算幾何|てんいちけってい]] | ||
2008年11月13日 (木) 12:42時点における最新版
【てんいちけってい (point location)】
2次元の場合, 与えられた平面上の点からなる直線分の平面グラフに対して, 質問点が与えられたとき, を含む面(領域)を求める問題. 地理情報データベースなどで基本的な問題としてしばしば生じる. 高次元の問題も同様に定義される. 質問に高速に応えるため, 通常は前処理が施され, アルゴリズムの性能は, 前処理時間, 記憶領域, 応答時間の3点を総合して評価される. スラブ法, バケット法, 橋渡しチェイン法, 残存化スラブ法などが有名である.
