OR事典

領域木

読み方：りょういきぎ
【英】：range tree

領域探索をサポートするデータ構造. 平面上の与えられた点の集合に対して, 軸に平行な質問長方形が与えられたとき, に含まれるの点を列挙する問題に用いられる. 平面上の点集合の領域を座標の中央値に基づいて二分割を繰り返し, その分割に対応する二分木を作る. さらに各ノードには対応する対象領域内にある点をすべて記憶しておく. これを領域木という. すると, 軸に平行な質問長方形が与えられたとき, %の区間が互いに共通部分をもたない区間の和集合として表現されるが, その区間に対応するノードで1次元の探索をすることでに含まれるの点を効率的に列挙できる.

「OR事典」の他の用語

計算幾何：

組合せ最適化問題  美術館監視問題  計算幾何学  記号摂動  重み最小三角形分割  領域探索  領域木