Loading article…
グラハムのスキャンは、平面上の有限の点の集合の凸包を時間計算量 O ( n log n ) で見つける方法です。この方法は、1972 年にオリジナルのアルゴリズムを発表したロナルド グラハムにちなんで名付けられました。[1]このアルゴリズムは、境界に沿って並べられた凸包のすべての頂点を見つけます。スタックを使用して、境界の凹みを効率的に検出して削除します。
アルゴリズム
このアルゴリズムの最初のステップは、最も低い y 座標を持つ点を見つけることです。最も低い y 座標がセット内の複数の点に存在する場合、候補の中から最も低い x 座標を持つ点を選択する必要があります。この点をPと呼びます。このステップにはO ( n ) かかります。ここで、n は問題となる点の数です。
次に、点の集合を、点Pと x 軸との角度が大きくなる順に並べ替える必要があります。これには、ヒープソート(O( n log n )) などの汎用ソート アルゴリズムが適しています。
角度の順序でソートする場合、角度を計算する必要はありません。区間 内で単調な角度の任意の関数を使用できます。 余弦はドット積を使用して簡単に計算できます。また、直線の傾きを使用することもできます。 数値の精度が問題になる場合は、ソート アルゴリズムで使用される比較関数で、外積の符号を使用して相対角度を決定できます。
![{\displaystyle [0,\pi ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e2a912eda6ef1afe46a81b518fe9da64a832751)
複数の点が同じ角度にある場合は、距離を増やして同点を解消するか (点が同じ光線上にあるため、計算を容易にするためにユークリッド距離ではなくマンハッタン距離またはチェビシェフ距離を使用できます)、最も遠い点以外のすべての点を削除します。
アルゴリズムは、ソートされた配列内の各ポイントを順に検討して進みます。各ポイントについて、まず、そのポイントの直前の 2 つのポイントからの移動が左折か右折かを判断します。右折の場合、最後から 2 番目のポイントは凸包の一部ではなく、凸包の「内側」にあります。次に、最新のポイントと、そのポイントの直前の 2 つのポイントのセットに対して同じ判断が行われ、それが「左折」セットに遭遇するまで繰り返されます。その時点で、アルゴリズムはソートされた配列内のポイント セットの次のポイント (凸包の内側にあると判明したポイントを除く) に進みます。これらのポイントを再度検討する必要はありません。(どの段階でも 3 つのポイントが同一線上にある場合は、それを破棄するか報告するかを選択できます。一部のアプリケーションでは、凸包の境界上にあるすべてのポイントを見つける必要があるためです。)
3 つの点が「左折」または「右折」のどちらを構成するかを判断するには、2 つの線分間の実際の角度を計算する必要はなく、実際には単純な演算だけで実行できます。3 つの点、、について、 2 つのベクトルとの外積のz座標を計算します。これは、式 で与えられます。結果が 0 の場合、点は同一直線上にあります。結果が正の場合、3 つの点は「左折」または反時計回りの方向を構成し、そうでない場合は「右折」または時計回りの方向を構成します (反時計回りの番号の付いた点の場合)。
このプロセスは最終的に開始時点に戻り、その時点でアルゴリズムが完了し、スタックには凸包上の点が反時計回りの順序で含まれるようになります。
時間計算量
点のソートには、時間計算量が O( n log n ) かかります。ループの時間計算量は、各点について、前の点のいずれかが「右折」しているかどうかをチェックするために戻るため、O( n 2 ) であるように見えるかもしれませんが、実際には、各点はある意味で最大 2 回しか考慮されないため、 O( n ) です。各点は、「左折」の点として (アルゴリズムはその後次の点に進むため)、および「右折」の点として (その点が削除されるため) 1 回だけ出現できます。ソートにかかる時間が、実際に凸包を計算する時間の大部分を占めるため、全体的な時間計算量は O( n log n ) になります。
擬似コード
以下の擬似コードでは、関数 ccw を使用しています。3 つの点が反時計回りに回転する場合は ccw > 0、時計回りの場合は ccw < 0、共線の場合は ccw = 0 です。(実際のアプリケーションでは、座標が任意の実数の場合、関数は浮動小数点数の正確な比較を必要とし、ほぼ共線的な点の数値特異性に注意する必要があります。)
次に、結果を に保存しますstack。
points を点のリスト
とする。stack = empty_stack()とする。
最も低いy座標と最も左の点（P0と呼ばれる）
を見つけ、P0で極角で点をソートします。複数の点が同じ極角を持つ場合は、最も遠い点のみを保持します。
ポイントインポイントの場合:
# この点に到達するまで時計回りに回すと、スタックから最後の点がポップされます
count stack > 1 かつccw (next_to_top(stack), top(stack), point) <= 0
の場合:スタックを
ポップし、ポイントをスタックの
末尾にプッシュします。
これで、スタックには凸包が含まれ、ポイントは反時計回りに向いており、P0 が最初のポイントになります。
ここでは、next_to_top()スタックを変更せずにスタックの最上部から 1 つ下の項目を返す関数、同様にtop()最上位の要素を返す関数を示します。
この疑似コードは、『Introduction to Algorithms』から改変したものです。
注記
同じ基本的な考え方は、入力が角度ではなくx座標でソートされ、船体が2段階で計算されてそれぞれ船体の上部と下部を生成する場合にも機能します。この変更はAMアンドリューによって考案されました。[2] これはグラハムのスキャンと同じ基本的な特性を持っています。[3]
グラハムのオリジナルの記述では、凸包の頂点の1つではなく、凸包の内部の点を中心にソートしていました。 [1]ソートアルゴリズムのピボットポイントを同じように選択すると、グラハムスキャンの残りの手順を実行するのではなく、この点を中心にソートされた順序で他のすべての点を接続すると、入力の多角形化である星型の多角形が生成されます。 [4]
グラハムのスキャンで使用されるスタック技術は、すべての最も近い小さな値の問題のスタック技術と非常によく似ており、すべての最も近い小さな値に対する並列アルゴリズムも（グラハムのスキャンのように）ソートされた点のシーケンスの凸包を効率的に計算するために使用できます。[5]
数値的堅牢性
数値の堅牢性は、有限精度の浮動小数点コンピュータ演算を使用するアルゴリズムで対処すべき問題です。2004 年の論文では、特に Graham スキャンの実装に使用できる単純な増分戦略が分析されました。[6]この論文の目的は、アルゴリズムを具体的に分析することではなく、計算幾何学における浮動小数点計算によって何が、どのように失敗する可能性があるかを示す教科書的な例を提供することでした。[6]その後、D. Jiang と NF Stewart [7]はこれを詳しく説明し、後方誤差分析を使用して2 つの主要な結論を導きました。1 つ目は、凸包は条件付きの問題であるため、妥当な誤差範囲内で答えを生成するアルゴリズムが期待できるということです。2 つ目は、Graham-Fortune (数値安定性に関する Steven Fortune のアイデア[8]を取り入れたもの) と呼ばれる Graham スキャンの修正が、有限精度と不正確なデータの問題を「可能な限り」克服することを示しています。
参照
参考文献
- ^ ab Graham, RL (1972). 「有限平面集合の凸包を決定するための効率的なアルゴリズム」(PDF) .情報処理レター. 1 (4): 132–133. doi :10.1016/0020-0190(72)90045-2.
- ^ Andrew, AM (1979). 「2次元の凸包のためのもう1つの効率的なアルゴリズム」. Information Processing Letters . 9 (5): 216–219. doi :10.1016/0020-0190(79)90072-3.
- ^ マーク・デ・バーグ;チョン、オトフリート。ヴァン・クレベルド、マーク。オーバーマーズ、マーク (2008)。計算幾何学アルゴリズムとアプリケーション。ベルリン：シュプリンガー。 2–14ページ。土井：10.1007/978-3-540-77974-2。ISBN 978-3-540-77973-5。
- ^ Arkin, Esther M.; Fekete, Sándor P.; Hurtado, Ferran; Mitchell, Joseph SB; Noy, Marc; Sacristán, Vera; Sethia, Saurabh (2003)。「点集合の反射性について」。Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (編)。離散幾何学と計算幾何学: グッドマン・ポラック記念論文集。アルゴリズムと組合せ論。第 25 巻。ベルリン: Springer。pp. 139–156。doi : 10.1007 /978-3-642-55566-4_6。ISBN 978-3-642-62442-1.MR2038472 。
- ^ Berkman, Omer; Schieber, Baruch ; Vishkin, Uzi (1993). 「最も近い小さい値をすべて見つけることに基づく最適な二重対数並列アルゴリズム」. Journal of Algorithms . 14 (3): 344–370. CiteSeerX 10.1.1.55.5669 . doi :10.1006/jagm.1993.1018. 。
- ^ ab Kettner, Lutz; Mehlhorn, Kurt; Pion, Sylvain; Schirra, Stefan; Yap, Chee (2008). 「幾何学計算における堅牢性の問題の教室での例」(PDF) .計算幾何学. 40 (1): 61–78. doi : 10.1016/j.comgeo.2007.06.003 .(以前のバージョンは 2004 年の ESA'2004 で報告されました)
- ^ D. Jiang および NF Stewart、「計算幾何学における後方誤差解析」、Wayback Machineに 2017-08-09 にアーカイブ、計算科学とその応用 - ICCSA 2006コンピュータサイエンス講義ノートシリーズの第 3980 巻、pp 50–59
- ^ フォーチュン、スティーブン (1989)。「2 次元における点集合三角形分割の安定維持」(PDF)。第 30 回コンピュータ サイエンスの基礎に関する年次シンポジウム。第 30 巻。pp. 494–499。doi : 10.1109/ SFCS.1989.63524。ISBN 0-8186-1982-12013年7月28日時点のオリジナル（PDF）よりアーカイブ。
さらに読む
- Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. 「33.3: 凸包の検出」.アルゴリズム入門(第 2 版). MIT Press および McGraw-Hill. pp. 949–955. ISBN 0-262-03293-7。