区間木
区間木またはインターバル木（英: Interval tree）は、区間を保持するための木構造のデータ構造の一種。計算幾何学のアルゴリズム。特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。似たものに区分木（英: Segment tree, segtree）があるが別物である。
基本的手法
[編集]単純なケースとして、区間が互いにオーバーラップしないなら、単純な2分木で表すことができ、クエリにかかる時間は O(log n) となる。しかし、区間同士がオーバーラップするなら、始点でソートする場合と終点でソートする場合で順序が異なることになるので、挿入時に2つの区間をどう比較すべきかが問題となる。素朴な方法としては、同時に2つの木を作り、一方は始点でソートし、もう一方は終点でソートすればよい。これを使ってクエリを行うと、それぞれの木で O(log n) の時間でオーバーラップする可能性のある区間をリストアップできるが、その結果をマージする必要があって、それには O(n) の時間がかかる。つまりクエリに対して O(n + log n) = O(n) の時間がかかることになり、力まかせ探索と比較すると全く改善されていない。
区間木はこの問題を解決するものである。以下では 'centered interval tree' と 'augmented tree' という2種類の設計を解説する。
Centered interval tree
[編集]クエリにかかる時間は O(log n + m) となる（n は格納されている区間の総数、m は報告される結果の総数）。構築には O(n log n) の時間がかかり、メモリ使用量は O(n) となる。
構築
[編集]数直線上に n 個の区間があるとき、これらを表すデータ構造を構築し、別の点や区間とオーバーラップする全ての区間を効率的に検索したいとする。
まず、全ての区間が含まれる範囲を特定し、その中央の x_center で分割する（x_center で分割するのは、木構造をなるべく平衡にするため）。これによって、区間は3種類に分類される。x_center の左側にある区間群を S_left、x_center の右側にある区間群を S_right、x_center にオーバーラップする区間群を S_center とする。
S_left と S_right に属する区間群は同様の方式で再帰的に分割していき、左右に区間が全く残らない状態にする。
S_center に属する区間群（中央点にオーバーラップしている区間群）は、区間木内のノードにリンクされた別のデータ構造に格納される。このデータ構造は2つのリストから構成されていて、1つは区間群を始点でソートしたリスト、もう1つは区間群を終点でソートしたリストである。
結果として構築される2分木のノードには、以下のようなデータが格納される。
- 中央点の位置
- 区間全体が中央点の左側にある区間群に対応したノードへのポインタ
- 区間全体が中央点の右側にある区間群に対応したノードへのポインタ
- 中心点とオーバーラップする全区間を始点でソートしたリスト
- 中心点とオーバーラップする全区間を終点でソートしたリスト
検索（クエリ）
[編集]以上のように構築されたデータ構造があるとき、区間または点についてのクエリを与えられると、その入力とオーバーラップする全ての区間の集合を返す。
区間
[編集]区間 R が入力として与えられたとき、それを点を入力として与えられた場合に還元することができる。まず、始点か終点が R の区間内にある区間を全て探す。1次元の場合、各区間の始点と終点で構成された単純な木構造を使えばよい。このとき、各点には対応する区間へのポインタを付与しておく。
この O(log n) の探索によって、考慮すべき最小と最大の点が明らかとなる。この範囲内の各点には区間が対応していて、それがクエリの区間とオーバーラップしているので、解に加える。ただし、始点も終点も R に含まれる区間も考えられるので、二重に登録しないよう注意が必要である。これを防ぐには、各区間を表すデータ構造にフラグを用意しておいて、解に加えられたときにそのフラグを立てればよい。
以上でまだ考慮されていない区間は、R が完全に含まれてしまうような区間である（始点も終点も R の中にはない）。このような区間を探すには、R 内の任意の点について下記に示す点クエリのアルゴリズムを実施すればよい（ここでも、二重に登録しないよう注意が必要である）。
点
[編集]次に点 x が入力として与えられた場合を考える。通常の2分木を走査するのと同様の再帰的アルゴリズムで木構造を走査する。各ノードについて x とそのノードの中央点である x_center を比較する。x が x_center より小さい場合、左側の S_left を調べる。x が x_center よりも大きい場合、右側の S_right を調べる。
根ノードから葉ノードまで、走査していく過程で、それぞれのノードの S_center に含まれる区間群を処理する。x が x_center より小さい場合、S_center にある区間は必ず終点が x より大きい（そうでないと x_center とオーバーラップできない）。したがって、S_center にある区間群のうち x より始点が小さい区間を探せばよい。S_center に対応するデータ構造はすでにあるのでそれを使い、この場合は始点だけを見ればいいので始点でソートされたリストを調べる。始点が x より小さい区間は、必ず x を含んでいる（終点は x_center より大きく、x_center は x より大きいため）。したがって、始点でソートされたリストを先頭から順に見ていき、始点が x より小さいものを出力に加える（始点が x を超えた時点で終了）。
同様に x が x_center より大きい場合、S_center にある区間群は全て始点が x より小さいことがわかっているので、終点でソートされたリストを使って、終点が x より大きい区間を探せばよい。
x が x_center と同一の場合、S_center にある区間群は全て解に含めることができ、しかもそれ以降の木構造の走査をする必要がない。
高次元
[編集]区間木はより高次の N 次元に拡張でき、クエリ時間と構築時間は1次元と同じで、メモリ使用量は O(n log n) となる。
まず、N次元の領域探索木を構築し、クエリの領域 R に始点や終点が含まれる全ての区間を効率的に検索できるようにする。そのような領域が明らかになったら、残る問題はクエリの領域を内包する領域を探す方法である。そのようなオーバーラップを探すにはN次元の区間木を構築し、いずれかの座標軸について R と交差するかどうかを調べる。例えば、2次元の場合、X軸についての区間木を構築し、四角形などの領域 R がクエリとして与えられる。そして、同時にY軸についての区間木に対しても同様にクエリを処理する。
次元があがると、それに対応して区間木も余分に必要になる。木構造を走査する際に、オーバーラップを探すために x と S_center の比較を行う。1次元の場合に2つのソートされたリストが使われていた部分に、領域探索木を構築する。これにより、S_center と領域 R のオーバーラップを効率的に検索できるようになる。
Augmented tree
[編集]別の手法は、Introduction to Algorithms, Second Edition[1]の 14.3 章（pp.331–317、First Edition は15.3章）に記述がある。
挿入と削除にかかる時間は O(log n) である（n は区間の総数）。
これは、単純な順序木（例えば2分探索木や平衡2分探索木）を使うもので、ノードの順序は各区間の始点（下限の値）に従い、各ノードには区間の終点（上限）とそのノード配下の部分木全体の最大上限値が格納される。この情報を挿入・削除に際して保つには、O(h) ステップ（h はそのノードの高さ）の処理を行えばよく、上位ノードに対して最大値の更新をしていく。
2つの区間 A と B がオーバーラップするのは、A.low ≤ B.high と A.high ≥ B.low が同時に成り立つ場合だけである。この木構造でオーバーラップを探して走査していく場合、以下のような場合を即座に除外できる。
- 右の子ノードの始点（下限）がクエリの終点（上限）より大きい場合、それ以降の部分木は走査する必要がない。
- 最大上限値がクエリの始点より小さい部分木は走査する必要がない。
区間は全体としては、まず始点の値でソートされ、次いで終点の値でソートされていることになる。この順序付けを利用して区間の二重登録を防ぐことができる。区間の挿入は O(log n) だが、二重登録の検出には O(k + log n) がかかる（k は新たな区間とオーバーラップしている区間数）。
高次元
[編集]この木構造を高次元に拡張するには、木の各レベルで対応する次元を周期的に変化させればよい。例えば、2次元の場合、奇数レベルではX軸の範囲を扱い、偶数レベルではY軸を扱う。ただし、このような木構造で木の回転によって平衡を保つアルゴリズムは、あまり明らかではない。
脚注
[編集]- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7
関連項目
[編集]参考文献
[編集]- Mark de Berg; Marc van Kreveld; Mark Overmars; Otfried Schwarzkopf (2000). “Section 10.1: Interval Trees”. Computational Geometry (Second Revised ed.). Springer-Verlag. pp. 212-217. (centered interval tree). ISBN 3642096816. NCID BA45765321
- (日本語訳 M.ドパーグ、M.ファン.クリベルト、M.オーバマーズ、O.シュワルツコップ「10.1:区間木、10.3:区間木」『コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用』近代科学社、2000年（原著1997年）、pp.260-268,274-282頁。ISBN 4764903881。)
- Franco P. Preparata; Michael Ian Shamos (1985). Computational Geometry: An Introduction. augmented tree. Springer-Verlag. ISBN 0387961313. NCID BA00039338. ISBN 3540961313