スイープラインアルゴリズム

ボロノイ図を構築するためのスイープライン技法であるフォーチュンのアルゴリズムのアニメーション。

計算幾何学において、スイープラインアルゴリズムまたは平面スイープアルゴリズムは、概念的なスイープラインまたはスイープ面を使用してユークリッド空間内のさまざまな問題を解決するアルゴリズムパラダイムです。これは、計算幾何学における重要な手法の 1 つです。

このタイプのアルゴリズムの背後にある考え方は、線 (多くの場合は垂直線) が平面上をスイープまたは移動し、ある点で停止することを想定することです。幾何学的操作は、スイープラインが停止するたびに交差するかスイープラインのすぐ近くにある幾何学的オブジェクトに制限され、線がすべてのオブジェクトを通過すると完全なソリューションが得られます。

歴史

このアプローチは、コンピュータグラフィックスのレンダリングのスキャンラインアルゴリズムにまで遡ることができ、その後、集積回路レイアウト設計の初期のアルゴリズムでこのアプローチが活用されました。集積回路の幾何学的記述は、全体の記述がメモリに収まらないため、並列ストリップで処理されました。^[^要出典^]

アプリケーション

このアプローチの応用により、 1976 年にShamosと Hoey が平面上の線分の交差のアルゴリズムを発表し、幾何学アルゴリズムの計算複雑性に飛躍的な進歩がもたらされました。特に、彼らは、スキャンラインアプローチと効率的なデータ構造 (自己バランス型バイナリサーチツリー) を組み合わせることで、平面上の $N個の線分間の交差があるかどうかを$ $O$ $($ $N$ $log$ $N$ $)$ の時間複雑度で検出できるようになることを説明しました。^[1]密接に関連するBentley–Ottmann アルゴリズムは、スイープライン手法を使用して、平面上の任意の $N個の線分間の$ $K 個$ の交差すべてを、 $O(($ $N$ $+$ $K$ $) log$ $N$ $)の時間複雑度と$ $O($ $N$ $)$ の空間複雑度で報告します。^[2]

それ以来、このアプローチは、ボロノイ図の構築(フォーチュンのアルゴリズム) やドロネー三角形分割、多角形に対するブール演算など、計算幾何学における多くの問題に対する効率的なアルゴリズムの設計に使用されてきました。

一般化と拡張

トポロジカルスイープは、処理ポイントの順序付けが単純な平面スイープの一種であり、ポイントを完全にソートする必要がありません。これにより、一部のスイープラインアルゴリズムをより効率的に実行できます。

幾何学アルゴリズムを設計するための回転ノギス技術は、入力平面の射影双対における平面スイープの一形態として解釈することもできる。射影双対の一形態は、1 つの平面における直線の傾きを双対平面における点のx座標に変換するため、回転ノギスアルゴリズムによって実行される、傾きでソートされた順序での直線の進行は、平面スイープアルゴリズムにおけるx座標でソートされた点の進行と双対である。 ^{[引用が必要]}

スイープアプローチは高次元に一般化できる可能性がある。^[3]

参考文献

^ Shamos, Michael I. ; Hoey, Dan (1976)、「幾何学的交差問題」、Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76)、pp. 208–215、doi :10.1109/SFCS.1976.16、S2CID 124804。
^ Souvaine, Diane (2008)、スイープラインアルゴリズムを使用した線分の交差(PDF)。
^ Sinclair, David (2016-02-11). 「凸包とドロネー三角形分割を計算するための 3D スイープハルアルゴリズム」. arXiv : 1602.04707 [cs.CG].

[1] Shamos, Michael I. ; Hoey, Dan (1976)、「幾何学的交差問題」、Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76)、pp. 208–215、doi :10.1109/SFCS.1976.16、S2CID 124804。

[2] Souvaine, Diane (2008)、スイープラインアルゴリズムを使用した線分の交差(PDF)。

[3] Sinclair, David (2016-02-11). 「凸包とドロネー三角形分割を計算するための 3D スイープハルアルゴリズム」. arXiv : 1602.04707 [cs.CG].