領域木のソースを表示
←
領域木
ナビゲーションに移動
検索に移動
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
この操作は、以下のグループに属する利用者のみが実行できます:
登録利用者
。
このページは編集や他の操作ができないように保護されています。
このページのソースの閲覧やコピーができます。
'''【りょういきぎ (range tree)】''' 領域探索をサポートするデータ構造. 平面上の与えられた$n$点の集合$S$に対して, $x,y$軸に平行な質問長方形$Q$が与えられたとき, $Q$に含まれる$S$の点を列挙する問題に用いられる. 平面上の点集合の領域を$x$座標の中央値に基づいて二分割を繰り返し, その分割に対応する二分木を作る. さらに各ノードには対応する対象領域内にある点をすべて記憶しておく. これを領域木という. すると, $x,y$軸に平行な質問長方形$Q$が与えられたとき, %$Q$の$x$区間が互いに共通部分をもたない区間の和集合として表現されるが, その区間に対応するノードで1次元の探索をすることで$Q$に含まれる$S$の点を効率的に列挙できる.
領域木
に戻る。
案内メニュー
個人用ツール
ログイン
名前空間
ページ
議論
変種
表示
閲覧
ソースを表示
履歴表示
その他
検索
案内
メインページ
コミュニティ・ポータル
最近の出来事
最近の更新
おまかせ表示
ヘルプ
ORWikiへのお問い合わせ
OR学会HP
OR学会アーカイブ集
ツール
リンク元
関連ページの更新状況
特別ページ
ページ情報