区間木

OR事典

区間木

読み方：くかんぎ
【英】：interval tree

整数区間を根に対応させ, 以下その区間をほぼ二等分しながら左右の子に対応させていきながら単位長さの区間の集合に分割する分割法を木構造のデータ構造で表現したもの. 区間木のノードにはそれぞれ分割に対応する整数区間が付随する. さらにの与えられた部分区間の集合をこの対応に基づいて適切に記憶することにより, 区間の集合に対する探索をサポートする効率的なデータ構造が得られる. それを用いれば, 個の区間の集合に対して, 質問点を含む の区間をすべて求める問題などが区間木を用いて効率的に解ける.

「OR事典」の他の用語

計算幾何：

凸多面体  凸集合  動的ボロノイ図  区間木  厳密計算法  双対変換  可視グラフ

ウィキペディア

区間木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/11/22 01:51 UTC 版)

区間木またはインターバル木（英: Interval tree）は、区間を保持するための木構造のデータ構造の一種。計算幾何学のアルゴリズム。特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。似たものに区分木（英: Segment tree, segtree）があるが別物である。