地点の位置

O(log n ) 時間を実現する最も単純で初期のデータ構造は、1976 年にDobkinとLiptonによって発見されました。これは、 Sの各頂点を通る垂直線を使用してS を細分化することに基づいています。連続する 2 つの垂直線の間の領域はスラブと呼ばれます。各スラブは、左から右に完全にスラブを横切る交差しない線分によって分割されていることに注意してください。スラブ内の連続する 2 つの線分の間の領域は、Sの一意の面に対応します。したがって、点位置問題を 2 つのより単純な問題に縮小します。^{[ 2 ]}

1. 平面を垂直なスラブに分割した場合、与えられた点がどのスラブに含まれるかを判定する。
2. 左から右へ完全に横断する、互いに交差しない線分によって領域に分割された平板が与えられたとき、与えられた点がどの領域に含まれるかを判定する。

最初の問題は、垂直線のx座標に対する二分探索によって O(log n ) 時間で解決できます。2 番目の問題も、二分探索によって O(log n ) 時間で解決できます。その方法を確認するには、セグメントが交差せず、スラブを完全に横断しないため、各スラブ内でセグメントを垂直方向にソートできることに注目してください。このアルゴリズムは対数時間で点の位置を特定でき、実装も容易ですが、各スラブがセグメントのかなりの割合を横断する可能性があるため、スラブとスラブ内に含まれる領域を構築するために必要なスペースは O( n ² ) にもなる可能性があります。^{[ 2 ]}

複数の著者が、隣接する2つのスラブを横切るセグメントはほとんど同じであることに気付きました。そのため、データ構造のサイズを大幅に削減できます。より具体的には、SarnakとTarjanは、垂直線lを平面上で左から右に走査し、 lと交差するセグメントを永続的な赤黒木に保持します。これにより、O(log n )のクエリ時間を維持しながら、ストレージスペースをO( n )に削減できます。 ^{[ 3 ]}

（垂直方向の）単調チェーンとは、パスに沿ってy座標が決して増加しないパスのことです。単純な多角形は、最初の頂点と最後の頂点が共通の 2 つの単調チェーンによって形成される場合、（垂直方向の）単調です。平面の分割にいくつかの辺を追加して、すべての面を単調にすることができ、単調分割と呼ばれるものが得られます。このプロセスでは分割に頂点は追加されません（したがって、サイズは O( n ) のままです）。また、平面掃引によってO( n log n ) 時間で実行できます（多角形の三角形分割を使用して線形時間で実行することもできます）。したがって、このセクションで行っているように、データ構造を単調分割の場合に限定しても、一般性は失われません。

スラブ分解の弱点は、垂直線が分解に余分なセグメントを作成するため、O( n ) のストレージスペースを実現するのが難しいことです。Herbert Edelsbrunner、Leonidas J. Guibas、Jorge Stolfi は、単調分割のエッジのみを使用する最適なデータ構造を発見しました。そのアイデアは、分割を分割するために垂直線を使用する代わりに、垂直単調チェーンを使用することです。^{[ 4 ]}

この一般的なアイデアを実際の効率的なデータ構造に変換するのは簡単な作業ではありません。まず、分割をほぼ同じサイズの2つの半分に分割する単調チェーンを計算できる必要があります。次に、一部のエッジが複数の単調チェーンに含まれる可能性があるため、ストレージスペースがO(n)であることを保証するために注意する必要があります。第三に、点が単調分割の左側にあるか右側にあるかをテストするには、単純に実行するとO( n )の時間がかかります。^{[ 4 ]}

最初の 2 つの問題を解決する方法の詳細は、この記事の範囲外です。ここでは、3 番目の問題に対処する方法について簡単に説明します。バイナリ サーチを使用すると、点が単調チェーンの左側にあるか右側にあるかを O(log n ) 時間でテストできます。点の位置を実際に決定するには、O(log n ) チェーンを通して別のネストされたバイナリ サーチを実行する必要があるため、クエリ時間は O(log² n) になります。O(log n ) のクエリ時間を実現するには、異なる単調チェーンのエッジ間にポインタを保持する分数カスケードを使用する必要があります。^{[ 4 ]}

m個の頂点を持つ多角形は、m –2 個の三角形に分割できます。これは、三角形から始める帰納法によって示すことができます。多角形を効率的に三角形分割するアルゴリズムは多数あり、最速のものは最悪の場合 O( n ) の時間で済みます。したがって、分割の各多角形を三角形に分解し、データ構造を三角形のみで構成される分割の場合に限定することができます。Kirkpatrick は、O( n ) のストレージスペースと O(log n ) のクエリ時間で三角形分割された分割内の点位置のデータ構造を提供しています。 ^{[ 5 ]}

基本的な考え方は、三角形の階層構造を構築することです。クエリを実行するには、まずクエリ点を含む最上位の三角形を見つけることから始めます。最上位の三角形の数は定数で制限されているため、この操作は O(1) 時間で実行できます。各三角形は、階層構造の次のレベルで交差する三角形へのポインタを持ち、ポインタの数も定数で制限されています。クエリは、レベルごとにクエリ点を含む三角形を見つけることで進めます。^{[ 5 ]}

データ構造は逆の順序、つまりボトムアップで構築されます。まず三角形分割から始め、削除する独立した頂点の集合を選択します。頂点を削除した後、分割を再三角形化します。分割は三角形によって形成されるため、貪欲アルゴリズムは、頂点の一定割合を含む独立した集合を見つけることができます。したがって、削除ステップの数は O(log n ) です。^{[ 5 ]}

この問題に対するランダム化アプローチは、台形分解または台形マップに基づいています。台形分解は、元の分割の各頂点から上下に垂直に弾丸を発射することによって得られます。弾丸はエッジに当たると停止し、分割内に新しいエッジを形成します。このようにして、元の分割の各頂点に対して新しい頂点を 2 つ追加し、エッジの数を 4 つ増やすだけなので、エッジと頂点が O( n ) 個だけのスラブ分解のサブセットが得られます。 ^{[ 6 ]}

台形分解は、元の細分化からセグメントをランダムな順序で 1 つずつ追加することによって構築できます。最初は (セグメントが追加される前)、台形分解は、細分化の境界ボックスである単一の台形で構成されます。以降の各ステップでは、点位置クエリを使用して、現在の台形分解内の次の線分の 1 つの端点を特定し、結果として得られた台形から同じセグメントを含む隣接する台形に移動して、それらを細分化して再結合し、より洗練された分解を形成します。この種のランダム化された増分ジオメトリ アルゴリズムによく使用される分析形式である逆解析は、各挿入で作成される台形の期待値が定数で制限され、したがって、点位置以外のこのアルゴリズムのステップの総数が線形であることを示しています。^{[ 6 ]}

このアルゴリズム内で実行される現在の細分化における点の位置は、アルゴリズムの最後に最終的な台形分解における点位置クエリに使用できるのと同じ構造を使用して取得できます。この点位置データ構造は、有向非巡回グラフの形式をとります。頂点は細分化のある時点で存在していた台形であり、有向エッジは細分化に含まれなくなった各台形を、それを置き換えた台形に接続します。点位置クエリは、このグラフ内のパスをたどることによって実行されます。最初の台形から開始し、各ステップでクエリ点を含む置き換え台形を選択し、置き換えられていない台形に到達するまで続けます。任意のクエリ点から開始するこの有向グラフの検索の期待深度は O(log n ) です。データ構造の空間は、この細分化プロセス全体で作成される台形の数に比例し、期待値は O( n ) です。^{[ 6 ]}