幾何学的問合せ問題

ウィキペディア小見出し辞書

幾何学的問合せ問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/19 02:37 UTC 版)

「計算幾何学」の記事における「幾何学的問合せ問題」の解説

一般には幾何学的探索問題として知られる幾何学的問合せ問題において、入力は探索空間と問合せ（クエリ）の二つの部分からなり、それらは問題事例に応じてさまざまなものがある。探索空間はふつう、複数の問合せに効果的に応答することができるように、前処理されている必要がある。 基本的な幾何学的問合せ問題としては、 範囲探索: 点の集合を前処理して、要求された領域の内側にある点の数を効果的に数えられるように整列する。 点配置: 空間のセル分割が与えられたとき要求された点がどのセルに配置されるかを効果的に解答できるようなデータ構造を導出する問題。 最近接近傍探索: 点の集合を前処理して、要求された点に最も近い点を効果的に見つけられるように並べ替える。 レイ・トレーシング: 空間内の物体の集合が与えられたとき、要求された半直線が最初にどの物体と交わるかを解答する効果的なデータ構造を求める問題。 などが挙げられる。探索空間を固定するとき、この類の問題に対する計算量は通常 探索に必要なデータ構造を構築するの必要な時間と空間、 問合せに応答するまでの時間（と場合によっては余分の空間） によって評価される。探索空間を変更することが許される場合については後述の#動的問題を参照。