「領域木」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (他の1人の利用者による、間の1版が非表示) | |||
| 2行目: | 2行目: | ||
領域探索をサポートするデータ構造. 平面上の与えられた<math>n\,</math>点の集合<math>S\,</math>に対して, <math>x,y\,</math>軸に平行な質問長方形<math>Q\,</math>が与えられたとき, <math>Q\,</math>に含まれる<math>S\,</math>の点を列挙する問題に用いられる. 平面上の点集合の領域を<math>x\,</math>座標の中央値に基づいて二分割を繰り返し, その分割に対応する二分木を作る. さらに各ノードには対応する対象領域内にある点をすべて記憶しておく. これを領域木という. すると, <math>x,y\,</math>軸に平行な質問長方形<math>Q\,</math>が与えられたとき, %<math>Q\,</math>の<math>x\,</math>区間が互いに共通部分をもたない区間の和集合として表現されるが, その区間に対応するノードで1次元の探索をすることで<math>Q\,</math>に含まれる<math>S\,</math>の点を効率的に列挙できる. | 領域探索をサポートするデータ構造. 平面上の与えられた<math>n\,</math>点の集合<math>S\,</math>に対して, <math>x,y\,</math>軸に平行な質問長方形<math>Q\,</math>が与えられたとき, <math>Q\,</math>に含まれる<math>S\,</math>の点を列挙する問題に用いられる. 平面上の点集合の領域を<math>x\,</math>座標の中央値に基づいて二分割を繰り返し, その分割に対応する二分木を作る. さらに各ノードには対応する対象領域内にある点をすべて記憶しておく. これを領域木という. すると, <math>x,y\,</math>軸に平行な質問長方形<math>Q\,</math>が与えられたとき, %<math>Q\,</math>の<math>x\,</math>区間が互いに共通部分をもたない区間の和集合として表現されるが, その区間に対応するノードで1次元の探索をすることで<math>Q\,</math>に含まれる<math>S\,</math>の点を効率的に列挙できる. | ||
| + | |||
| + | |||
| + | [[Category:計算幾何|りょういきぎ]] | ||
2008年11月14日 (金) 09:38時点における最新版
【りょういきぎ (range tree)】
領域探索をサポートするデータ構造. 平面上の与えられた点の集合に対して, 軸に平行な質問長方形が与えられたとき, に含まれるの点を列挙する問題に用いられる. 平面上の点集合の領域を座標の中央値に基づいて二分割を繰り返し, その分割に対応する二分木を作る. さらに各ノードには対応する対象領域内にある点をすべて記憶しておく. これを領域木という. すると, 軸に平行な質問長方形が与えられたとき, %の区間が互いに共通部分をもたない区間の和集合として表現されるが, その区間に対応するノードで1次元の探索をすることでに含まれるの点を効率的に列挙できる.
