ポイントの位置

点の位置の問題は、計算幾何学の基本的なテーマです。コンピュータ グラフィックス、地理情報システム(GIS)、動作計画、コンピュータ支援設計(CAD)など、幾何学データの処理を扱う分野で応用されています。

最も一般的な形式では、空間が互いに素な領域に分割されている場合、クエリ ポイントが存在する領域を決定するという問題があります。たとえば、特定のマウス クリックがグラフィカル ユーザー インターフェイスのどのウィンドウに含まれているかを決定する問題は、各ウィンドウの表示部分によって細分化されたポイント位置のインスタンスとして定式化できますが、このアプリケーションでは、汎用のポイント位置データ構造よりも特殊なデータ構造の方が適している可能性があります。^[1]もう 1 つの特殊なケースは、ポイントが単一のポリゴンの境界の内側、外側、または上にあるかどうかを判断する必要があるポリゴン内のポイントの問題です。

多くのアプリケーションでは、空間の同じパーティションに関して複数の異なるポイントの位置を決定する必要があります。この問題を効率的に解決するには、クエリ ポイントが与えられたときに、どの領域にクエリ ポイントが含まれているかをすばやく決定するデータ構造を構築すると便利です (例: Voronoi 図)。

平面の場合、面と呼ばれる複数のポリゴンで形成された平面のサブディビジョン Sが与えられ、どの面にクエリ ポイントが含まれているかを判断する必要があります。ポイント イン ポリゴンアルゴリズムを使用して各面を総当たりで検索することは可能ですが、通常、非常に複雑なサブディビジョンでは実行できません。いくつかの異なるアプローチにより、O ( n ) のストレージ スペースと O(log n ) のクエリ時間で最適なデータ構造が得られます。ここで、n はS内の頂点の総数です。簡単にするために、平面のサブディビジョンは正方形の境界ボックス内に含まれていると仮定します。

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) であることを保証する必要があります。3 番目に、点が単調な細分化の左側にあるか右側にあるかをテストするには、単純に実行すると 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(logn )のクエリ時間で提供します。^[5]

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

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

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

台形分解は、元の分割からセグメントを 1 つずつランダムな順序で追加することで構築できます。最初 (セグメントが追加される前) は、台形分解は 1 つの台形 (分割の境界ボックス)で構成されます。後続の各ステップでは、ポイント位置クエリを使用して、現在の台形分解内の次の線分の 1 つのエンドポイントを見つけ、次に、結果として得られた台形から同じセグメントを含む隣接する台形に移動し、それらを分割して再結合して、洗練された分解を形成します。この種のランダムな増分ジオメトリ アルゴリズムでよく使用される分析形式である逆分析では、挿入ごとに作成される台形の予想数が定数で制限されるため、ポイント位置以外のこのアルゴリズムのステップの合計数は線形であることが示されています。^[6]

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

2 を超える次元に対して線形空間と対数クエリ時間を備えた一般的なポイント位置データ構造は知られていません^{[引用が必要]}。したがって、クエリ時間またはストレージ スペースを犠牲にするか、あまり一般的ではないタイプの細分化に制限する必要があります。

3次元空間では、 O( nlogn )の空間を使用して、O(log²n)で点の位置クエリに応答できます。一般的な考え方は、細分化と各細分化頂点を含むn個の平行平面との交差に対応する、いくつかの平面点の位置データ構造を維持することです。この考え方を単純に使用すると、ストレージスペースがO( n² )に増加します。スラブ分解の場合と同様に、連続するデータ構造間の類似性を利用してストレージスペースをO(nlogn)に削減できますが、クエリ時間はO(log²n)に増加します。 [ ^7]

d次元空間では、面を ( d -1) 次元空間に再帰的に投影することで点の位置を解決できます。クエリ時間は O(log n ) ですが、ストレージ スペースは まで大きくなります。d次元データ構造の複雑さが高いため、特殊なタイプの細分化が研究されました。 ${\displaystyle O(n^{2^{d}})}$

重要な例の 1 つは、超平面の配置の場合です。n 個の超平面の配置ではO( n ^d ) 個のセルが定義されますが、 Chazelleの階層的切断 を使用すると、点の位置特定は O(log n ) 時間で O( n ^d ) のスペースで実行できます。

別の特殊なタイプの分割は、直線（または直交）分割と呼ばれます。直線分割では、すべてのエッジはd直交軸の 1 つに平行です。この場合、点の位置は O(log ^{d -1} n ) 時間で O( n ) のスペースで答えることができます。

• デ・バーグ、マーク。マーク・ヴァン・クレフェルト。マーク・オーヴァーマーズ;シュワルツコップ、オトフリート (2000)。 「第6章：ポイントの位置」。計算幾何学(改訂第 2 版)。スプリンガー・フェルラーグ。 121–146ページ。ISBN 3-540-65620-0。
• Bern, Marshall (1990). 「長方形の隠れ面除去」. Journal of Computer and System Sciences . 40 (1): 49– 69. doi : 10.1016/0022-0000(90)90018-G . MR  1047289.
• Dobkin, David ; Lipton, Richard J. (1976). 「多次元検索問題」SIAM Journal on Computing . 5 (2): 181– 186. doi :10.1137/0205015.
• Edelsbrunner, Herbert ; Guibas, Leonidas J. ; Stolfi, Jorge (1986). 「単調なサブディビジョンにおける最適なポイントの位置」SIAM Journal on Computing . 15 (2): 317– 340. doi :10.1137/0215023.
• カークパトリック、デビッド G. (1983)。 「平面細分における最適探索」。SIAM Journal on Computing。12 ( 1): 28– 35。CiteSeerX 10.1.1.461.1866。doi :10.1137 / 0212002。 
• Sarnak, Neil; Tarjan, Robert E. (1986). 「永続的な検索木を使用した平面点の位置特定」Communications of the ACM . 29 (7): 669– 679. doi : 10.1145/6138.6151 .

• Snoeyink, Jack (2004)。「第 34 章:「点の位置」」。Goodman , Jacob E.、O'Rourke, Joseph (編)。離散幾何学と計算幾何学のハンドブック(第 2 版)。Chapman & Hall/CRC。ISBN 1-58488-301-4。

• ストーニーブルック大学のポイントロケーションソースリポジトリ
• 計算幾何学アルゴリズムライブラリCGALにおけるポイント位置クエリ