多角形の三角測量

計算幾何学において、多角形の三角測量とは、多角形領域（単純な多角形） $Pを$ 三角形の集合に分割することである^[1]。すなわち、互いに交差しない内部を持つ三角形の集合を見つけ、その集合の和が $P$ となることを指す。

三角形分割は、平面直線グラフの特殊なケースとして考えることができます。穴や追加された点がない場合、三角形分割は最大の外平面グラフを形成します。

余分な頂点のないポリゴンの三角形分割

これまで、多角形を三角形に分割するためのアルゴリズムが数多く提案されてきました。

特別なケース

1 つの頂点から他のすべての非最近傍頂点への対角線を追加することによって、任意の凸多角形を線形時間で扇形三角形に三角形分割することは簡単です。

交差しない対角線で凸n角形を三角形に分割する方法の総数は（ n −2）番目のカタラン数であり、これは

{\frac {n(n+1)...(2n-4)}{(n-2)!}}

、

レオンハルト・オイラーが発見した公式。^[2]

単調な多角形は、 A . FournierとDY Montunoのアルゴリズム ^[3]またはGodfried Toussaintのアルゴリズム^[4]のいずれかを使用して線形時間で三角形分割することができます。

耳切りの方法

単純な多角形を三角形に分割する方法の 1 つは、2 つの耳の定理に基づいています。これは、少なくとも 4 つの頂点があり穴がない単純な多角形には、少なくとも 2 つの「耳」があるという事実に基づいています。耳とは、2 つの辺が多角形の端で、3 つ目の辺が完全に多角形の内側にある三角形のことです。^[5]次に、アルゴリズムは、そのような耳を見つけて、それを多角形から削除し (これにより、条件を満たす新しい多角形が作成されます)、三角形が 1 つだけになるまで繰り返します。

このアルゴリズムは実装が簡単ですが、他のアルゴリズムよりも遅く、穴のないポリゴンでしか機能しません。凸頂点と凹頂点のリストを別々に保持する実装では、 $O(n2)$ 時間で実行されます。この方法は、耳切り、または耳トリミングとして知られています。耳を切り落とす効率的なアルゴリズムは、Hossam ElGindy、Hazel Everett、Godfried Toussaintによって発見されました。^[6 $]$

単調な多角形の三角測量

$単純な多角形は、直線L$ に対して単調であるとは、 $L$ に直交する直線が多角形と最大 2 回交差する場合をいいます。単調な多角形は、2 つの単調なチェーンに分割できます。y 軸に対して単調な多角形は、y 単調と呼ばれます。n 頂点を持つ単調な多角形は、 $O($ $n$ $)$ 時間で三角形に分割できます。与えられた多角形が y 単調であると仮定すると、貪欲アルゴリズムは、可能な場合は常に対角線を追加しながら、 $多$ 角形の 1 つのチェーンを上から下まで移動することから始まります。^[1]このアルゴリズムが任意の単調な多角形に適用できることは容易にわかります。

非単調な多角形の三角形分割

多角形が単調でない場合は、スイープラインアプローチを使用して $、$ $O(nlogn) 時間で$ 単調なサブポリゴンに分割できます。このアルゴリズムでは、ポリゴンが単純である必要がないため、穴のあるポリゴンにも適用できます。一般に、 $この$ $アルゴリズムは、 O($ $n$ $)空間を使用して$ $、$ $O($ $nlogn$ $)$ 時間で $n$ 頂点の平面細分を三角形化できます。^[1]

三角分割の双対グラフ

$多角形P$ の三角形分割によく関連付けられる便利なグラフは、双対グラフです。 $P$ の三角形分割 $T P$ が与えられたとき、グラフ $G$ $($ $T$ $P$ $)は、$ $T$ $P$ の三角形を頂点集合とするグラフとして定義されます。2 つの頂点 (三角形) は、対角線を共有する場合にのみ隣接します。 $G$ $($ $T$ $P$ $)$ が最大次数 3 の木であることは容易にわかります。

計算の複雑さ

1988年まで、単純な多角形を $O(nlogn) 時間$ より速く三角形分割できるかどうかは、計算幾何学における未解決の問題でした。 $[$ ^1]その後、TarjanとVan Wyk (1988)は三角形分割のためのO(nloglogn)時間のアルゴリズムを発見し $、$ $[$ 7 $] その後 Kirkpatrick$ ^、 Klawe、Tarjan (1992)によって簡略化されました。^{[8]その後、複雑度} $O(nlog * n)$ (実際には線形時間と区別がつかない) $の$ いくつかの改良された方法が続きました。^[9]^[10]^[11]

バーナード・チャゼルは1991年に、提案されたアルゴリズムは非常に複雑ではあるが、任意の単純な多角形は線形時間で三角形に分割できることを示した。^[12]線形期待時間を持つより単純なランダム化アルゴリズムも知られている。^[13]

ザイデルの分解アルゴリズム^[10]とシャゼルの三角測量法については、Li & Klette (2011)で詳しく議論されている。^[14]

代数計算木モデルでは、穴のある $n$ 頂点多角形の三角形分割の時間計算量は $Ω($ $n$ $log$ $n$ $)$ の下限値を持つ。 ^[1]動的計画法を用いると、単純な多角形の異なる三角形分割の数を多項式時間で計算することができ、(この計数アルゴリズムに基づいて)多項式時間で一様ランダムな三角形分割を生成することもできる。^[15]しかし、穴のある多角形の三角形分割を数えることは#P 完全であるため、多項式時間で実行できる可能性は低い。^[16]

参照

参考文献

^ abcde Mark de Berg、Marc van Kreveld、Mark Overmars、およびOtfried Schwarzkopf (2000)、「3: Polygon Triangulation」、Computational Geometry (2nd ed.)、Springer-Verlag、pp. 45–61、ISBN 3-540-65620-0{{citation}}: CS1 maint: multiple names: authors list (link)
^ ピックオーバー、クリフォード A. (2009)、The Math Book、スターリング、p. 184
^ Fournier, Alain ; Montuno, Delfin Y. (1984)、「単純な多角形の三角分割と同等の問題」、ACM Transactions on Graphics、3 (2): 153–174、doi : 10.1145/357337.357341、ISSN 0730-0301、S2CID 33344266
^ Toussaint, Godfried T. (1984)、「単調な多角形を三角形に分割するための新しい線形アルゴリズム」、パターン認識レター、2 (3): 155–158、Bibcode :1984PaReL...2..155T、doi :10.1016/0167-8655(84)90039-4
^ マイスターズ、ゲイリー・ホスラー（1975）、「多角形には耳がある」、アメリカ数学月刊誌、82（6）：648–651、doi：10.2307/2319703、JSTOR 2319703
^ ElGindy, Hossam; Everett, Hazel; Toussaint, Godfried T. (1993)、「剪定と検索による耳のスライス」、パターン認識レター、14 (9): 719–722、Bibcode :1993PaReL..14..719E、doi :10.1016/0167-8655(93)90141-y
^ Tarjan, Robert E. ; Van Wyk, Christopher J. (1988)、「単純な多角形を三角化するO( n log log n ) 時間アルゴリズム」、 SIAM Journal on Computing、17 (1): 143–178、CiteSeerX 10.1.1.186.5949、doi :10.1137/0217010、MR 0925194
^ カークパトリック、デビッド G. ;クローウェ、マリア M. ;タージャン、ロバート E. (1992)、「シンプルなデータ構造によるO( n log log n ) 時間のポリゴン三角測量」、離散および計算幾何学、7 (4): 329–346、doi : 10.1007/BF02187846、MR 1148949
^ クラークソン、ケネス L. ;タージャン、ロバート; ヴァンワイク、クリストファー J. (1989)、「単純な多角形を三角化する高速ラスベガスアルゴリズム」、離散および計算幾何学、4 (5): 423–432、doi : 10.1007/BF02187741
^ ab Seidel, Raimund (1991)、「台形分解を計算し、多角形を三角形に分割するためのシンプルで高速な増分ランダム化アルゴリズム」、計算幾何学、1 : 51–64、CiteSeerX 10.1.1.55.5877、doi : 10.1016/0925-7721(91)90012-4
^ クラークソン、ケネス L. ; コール、リチャード;タージャン、ロバート E. (1992)、「台形図のランダム化並列アルゴリズム」、国際計算幾何学と応用誌、2 (2): 117–133、doi :10.1142/S0218195992000081、MR 1168952
^ シャゼル、バーナード（1991）、「線形時間での単純多角形の三角測量」、離散および計算幾何学、6（3）：485–524、doi：10.1007 / BF02574703、ISSN 0179-5376
^ アマト、ナンシー M. ;グッドリッチ、マイケル T. ; ラモス、エドガー A. (2001)、「単純な多角形を線形時間で三角分割するためのランダム化アルゴリズム」、離散および計算幾何学、26 (2): 245–265、doi : 10.1007/s00454-001-0027-x、ISSN 0179-5376
^ リー、ファジェ; Klette、Reinhard (2011)、Euclidean Shortest Paths、Springer、doi :10.1007/978-1-4471-2256-2、ISBN 978-1-4471-2255-5
^ エプスタイン、ピーター;サック、イェルク・リュディガー(1994)、「ランダムな三角形の生成」、ACM Transactions on Modeling and Computer Simulation、4 (3): 267–278、doi :10.1145/189443.189446、S2CID 14039662
^ Eppstein, David (2019)、「ポリゴンの三角形分割を数えるのは難しい」、Proc. 35nd Int. Symp. Computational Geometry、Leibniz International Proceedings in Informatics (LIPIcs)、vol. 129、Schloss Dagstuhl、pp. 33:1–33:17、arXiv : 1903.04737、doi : 10.4230/LIPIcs.SoCG.2019.33、ISBN 9783959771047、S2CID 75136891

外部リンク

Flash swf としてのデモ、スイープラインアルゴリズム。
Song Ho による OpenGL GLU テッセレータの説明

[bkos-1] Mark de Berg、Marc van Kreveld、Mark Overmars、およびOtfried Schwarzkopf (2000)、「3: Polygon Triangulation」、Computational Geometry (2nd ed.)、Springer-Verlag、pp. 45–61、ISBN 3-540-65620-0{{citation}}: CS1 maint: multiple names: authors list (link)

[2] ピックオーバー、クリフォード A. (2009)、The Math Book、スターリング、p. 184

[3] Fournier, Alain ; Montuno, Delfin Y. (1984)、「単純な多角形の三角分割と同等の問題」、ACM Transactions on Graphics、3 (2): 153–174、doi : 10.1145/357337.357341、ISSN 0730-0301、S2CID 33344266

[4] Toussaint, Godfried T. (1984)、「単調な多角形を三角形に分割するための新しい線形アルゴリズム」、パターン認識レター、2 (3): 155–158、Bibcode :1984PaReL...2..155T、doi :10.1016/0167-8655(84)90039-4

[5] マイスターズ、ゲイリー・ホスラー（1975）、「多角形には耳がある」、アメリカ数学月刊誌、82（6）：648–651、doi：10.2307/2319703、JSTOR 2319703

[6] ElGindy, Hossam; Everett, Hazel; Toussaint, Godfried T. (1993)、「剪定と検索による耳のスライス」、パターン認識レター、14 (9): 719–722、Bibcode :1993PaReL..14..719E、doi :10.1016/0167-8655(93)90141-y

[7] Tarjan, Robert E. ; Van Wyk, Christopher J. (1988)、「単純な多角形を三角化するO( n log log n ) 時間アルゴリズム」、 SIAM Journal on Computing、17 (1): 143–178、CiteSeerX 10.1.1.186.5949、doi :10.1137/0217010、MR 0925194

[8] カークパトリック、デビッド G. ;クローウェ、マリア M. ;タージャン、ロバート E. (1992)、「シンプルなデータ構造によるO( n log log n ) 時間のポリゴン三角測量」、離散および計算幾何学、7 (4): 329–346、doi : 10.1007/BF02187846、MR 1148949

[9] クラークソン、ケネス L. ;タージャン、ロバート; ヴァンワイク、クリストファー J. (1989)、「単純な多角形を三角化する高速ラスベガスアルゴリズム」、離散および計算幾何学、4 (5): 423–432、doi : 10.1007/BF02187741

[Seidel-10] Seidel, Raimund (1991)、「台形分解を計算し、多角形を三角形に分割するためのシンプルで高速な増分ランダム化アルゴリズム」、計算幾何学、1 : 51–64、CiteSeerX 10.1.1.55.5877、doi : 10.1016/0925-7721(91)90012-4

[11] クラークソン、ケネス L. ; コール、リチャード;タージャン、ロバート E. (1992)、「台形図のランダム化並列アルゴリズム」、国際計算幾何学と応用誌、2 (2): 117–133、doi :10.1142/S0218195992000081、MR 1168952

[12] シャゼル、バーナード（1991）、「線形時間での単純多角形の三角測量」、離散および計算幾何学、6（3）：485–524、doi：10.1007 / BF02574703、ISSN 0179-5376

[13] アマト、ナンシー M. ;グッドリッチ、マイケル T. ; ラモス、エドガー A. (2001)、「単純な多角形を線形時間で三角分割するためのランダム化アルゴリズム」、離散および計算幾何学、26 (2): 245–265、doi : 10.1007/s00454-001-0027-x、ISSN 0179-5376

[14] リー、ファジェ; Klette、Reinhard (2011)、Euclidean Shortest Paths、Springer、doi :10.1007/978-1-4471-2256-2、ISBN 978-1-4471-2255-5

[15] エプスタイン、ピーター;サック、イェルク・リュディガー(1994)、「ランダムな三角形の生成」、ACM Transactions on Modeling and Computer Simulation、4 (3): 267–278、doi :10.1145/189443.189446、S2CID 14039662

[16] Eppstein, David (2019)、「ポリゴンの三角形分割を数えるのは難しい」、Proc. 35nd Int. Symp. Computational Geometry、Leibniz International Proceedings in Informatics (LIPIcs)、vol. 129、Schloss Dagstuhl、pp. 33:1–33:17、arXiv : 1903.04737、doi : 10.4230/LIPIcs.SoCG.2019.33、ISBN 9783959771047、S2CID 75136891