ヒープ探索木（Priority Search Trees, PST）
１．概要
◆デモサンプル画面 <sample image of demo-program>
◆機能概要
ＸＹ平面上に分布するＮ個の点(X,Y)と質問領域[x0,x1][y0,∞]に対して、Y≧y0かつx0≦X≦x1である
点(X,Y)をＯ(k+logN)の手間で得られる。
ここで、ｋは条件を満たす点の数で、最大値はＮである。
点の追加、削除に対してもＯ(logN)の手間でPSTを再構成できる。必要なメモリ量はＯ(N)である。
◆ヒープ探索木の概要
ＸＹ平面上の点の集合に対して、Ｙ座標値でヒープを構成し、Ｘ座標値で平衡探索木を構成する。
◆方式
方式としては(1)McCreight方式と(2)place holder方式がある。
(1)McCreight方式では木のノード数がＮで済む。
１つのノードに２つ点を格納することがあるので描画には向かない。
ノード数が少ないのでメモリ効率が良い。
E.M.McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257.276, May 1985.
(2)place holder方式は木のノード数が２Ｎ−１であり、Ｎ−１個の葉ノードを除いて、
１つのノードに1個の点を格納するので、木を直感的に描画できる。
place holderノードに点を格納した部分はバランスが崩れて見える場合があるが、空のplace holderノードまで考慮するとバランスしている。
◆用途
(1)線分重なり判定 （区間の交差問題）
直線上のＮ個の線分[X,Y]が与えられた時に、質問線分[a,b]と交叉する全ての線分をＯ(k+logN)で得られる。
すなわち、線分[X,Y]に対して点(X,Y)を対応させて、Y≧a かつX≦bを満たす点が線分[a,b]と交叉する線分
である。
(2)長方形の重なり判定 （長方形交差問題）
水平線と垂直線を辺とするＮ個の長方形が与えられた時に、交差する長方形のペアを抽出する問題に
対して、走査線をずらしながら、線分の重なり判定と線分の追加削除を繰り返すことで、ペアを効率よく抽出できる。
◆機能概要
ＸＹ平面上に分布するＮ個の点(X,Y)と質問領域[x0,x1][y0,∞]に対して、Y≧y0かつx0≦X≦x1である
点(X,Y)をＯ(k+logN)の手間で得られる。
ここで、ｋは条件を満たす点の数で、最大値はＮである。
点の追加、削除に対してもＯ(logN)の手間でPSTを再構成できる。必要なメモリ量はＯ(N)である。
◆ヒープ探索木の概要
ＸＹ平面上の点の集合に対して、Ｙ座標値でヒープを構成し、Ｘ座標値で平衡探索木を構成する。
◆方式
方式としては(1)McCreight方式と(2)place holder方式がある。
(1)McCreight方式では木のノード数がＮで済む。
１つのノードに２つ点を格納することがあるので描画には向かない。
ノード数が少ないのでメモリ効率が良い。
E.M.McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257.276, May 1985.
(2)place holder方式は木のノード数が２Ｎ−１であり、Ｎ−１個の葉ノードを除いて、
１つのノードに1個の点を格納するので、木を直感的に描画できる。
place holderノードに点を格納した部分はバランスが崩れて見える場合があるが、空のplace holderノードまで考慮するとバランスしている。
◆用途
(1)線分重なり判定 （区間の交差問題）
直線上のＮ個の線分[X,Y]が与えられた時に、質問線分[a,b]と交叉する全ての線分をＯ(k+logN)で得られる。
すなわち、線分[X,Y]に対して点(X,Y)を対応させて、Y≧a かつX≦bを満たす点が線分[a,b]と交叉する線分
である。
(2)長方形の重なり判定 （長方形交差問題）
水平線と垂直線を辺とするＮ個の長方形が与えられた時に、交差する長方形のペアを抽出する問題に
対して、走査線をずらしながら、線分の重なり判定と線分の追加削除を繰り返すことで、ペアを効率よく抽出できる。
２．使用方法
◆ダウンロード（ダウンロードのページからもダウンロードできます）
sample07.zip 545 KB (558,914 バイト) ソース付き
展開後 PStree.exe 20,480 バイトト
pstreeDll.dll 696,320 バイト
２．１ インストール
(1)ダウンロードしたファイルを、任意のディレクトリに解凍します。
sample07フォルダの内容
(a) 使用許諾契約書.txt
(b) pstreeDll.dll
(c) PStree.exe
２．２ アンインストール
(1)インストール時に作成したディレクトリごとファイルを削除します。
２．３ 使用方法
PStree.exeをダブルクリック
※実行時には、.NetFramework3.5 が必要です。
sample07.zip 545 KB (558,914 バイト) ソース付き
展開後 PStree.exe 20,480 バイトト
pstreeDll.dll 696,320 バイト
２．１ インストール
(1)ダウンロードしたファイルを、任意のディレクトリに解凍します。
sample07フォルダの内容
(a) 使用許諾契約書.txt
(b) pstreeDll.dll
(c) PStree.exe
２．２ アンインストール
(1)インストール時に作成したディレクトリごとファイルを削除します。
２．３ 使用方法
PStree.exeをダブルクリック
※実行時には、.NetFramework3.5 が必要です。
３．開発環境
プログラムコードは、下記言語で作られています。
pstreeDll.dll は、 Visual Studio 2005 C++
PStree.exe は、 Visual Studio 2008 C#
pstreeDll.dll は、 Visual Studio 2005 C++
PStree.exe は、 Visual Studio 2008 C#