多角形の三角形分割

Summarize Timeline Fact Check

多角形の三角形分割アルゴリズムは多数提案されている。

ある頂点から伸びる全ての対角線により凸多角形は扇形分割され、これは三角形分割であるため、線形時間で三角形分割が可能である。

レオンハルト・オイラーによって、凸n角形の三角形分割の組合せの数は、交差しない対角線の数であり、${\displaystyle n-2}$ 番目のカタラン数 ${\displaystyle {\frac {(2n-4)!}{(n-1)!(n-2)!}}}$ である^[2]。

単純多角形を三角形分割する手法はtwo ears theoremに基づくものである。この定理は、4本以上の辺を持つ穴のない単純多角形は少なくとも2つの「耳（2辺が多角形の辺であり、残り1辺が多角形の内部に存在する三角形）」を持つという定理である^[3]。このアルゴリズムはこの「耳」を見つけ、その三角形を多角形から順に取り除くことで三角形分割を行う。

このアルゴリズムは実装が容易であるが他のアルゴリズムより遅く、穴を持たない多角形でしか動作しない。凸である頂点と凹である頂点を別のリストとして持つ実装の時間計算量はO(n²)である。この方法は耳刈り取り法もしくは耳取り除き法として知られるアルゴリズムで、Hossam ElGindy、Hazel Everett、Godfried Toussaintにより発見された^[4]。

単純多角形において、直線Lに垂直な任意の直線がその多角形と高々2点で交わるならば、その多角形は直線Lに関して単調である。単調多角形（英語版）は2つの単調連鎖に分割することができる。y軸に関して単調な多角形は、y単調と呼ばれる。n個の頂点を持つ単調多角形は、O(n)時間で三角形分割が可能である。与えられた多角形がy単調であると仮定した場合、貪欲法では、多角形の1つの連鎖を上から下へと辿りながら、可能な限り対角線を追加していくことから始まる。このアルゴリズムが任意の単調多角形に適用可能であることは容易にわかる。

1984年、アラン=フルニエとD.Y. Montunoによって、単調多角形は線形時間で三角形分割が可能であることが示された^[5]。Godfried Toussaintのアルゴリズムによっても、単調多角形は線形時間で三角形分割が可能である^[6]。

非単調多角形は以下のように単調多角形に分割できる。

各点について、隣り合う点が掃引線の同じ側にあるか、つまり「水平線や鉛直線を引いた場合に同じ側にあるかどうか」を確認する。もし同じ側にあれば掃引線を延長し、多角形と交差した点の辺の端点の内「違う側」の点間の線分で分割する。この処理を繰り返す。

（水平な）掃引線を下へと動かす場合に、両方の頂点が掃引線の上側にあり、下の図形が分割される場合がある。この場合、これから探索する図形が分割され、三角形分割のためにはそれぞれの図形に対して上記の処理を繰り返す必要がある。

このアルゴリズムを用いることで、多角形の三角形分割は${\displaystyle O(n\log n)}$時間で実行可能である。

多角形Pの三角形分割関連で有用なグラフに、三角形分割の双対グラフがある。Pの三角形分割T_Pが与えられたとき、T_Pの三角形を頂点として持ち隣接を辺として表すグラフG(T_P)が定義できる。G(T_P)は木であり、その最大次数は3である。

長きに渡って、単純多角形を${\displaystyle O(n\log n)}$時間より高速に三角形分割するアルゴリズムが未発見であった。その後、Tarjan & Van Wyk (1988)は${\displaystyle O(n\log \log n)}$時間で三角化を行うアルゴリズムを発見し^[7]、後にKirkpatrick Klaweとロバート・タージャンにより簡単化された^[8]。複数の改善により、${\displaystyle O(n\log ^{\ast }n)}$（実用上ほぼ線形時間）を実現している^[9][10][11]。

1991年にバーナード・チャゼルは非常な複雑なアルゴリズムではあるが、任意の単純多角形を線形時間で三角形分割するアルゴリズムを示した^[12]。また、乱択アルゴリズムを用いることで、平均計算時間が線形時間であるアルゴリズムも存在する^[13]。

ザイデルの分割アルゴリズムとチャゼルの三角形分割については、 Li & Klette (2011) が詳しい^[14]。

穴を持つn頂点の多角形の三角形分割の時間計算量の下界は${\displaystyle \Omega (n\log n)}$与えられている。

最小重み三角形分割は辺の長さの和が最小となるような三角形分割を求める問題である（三角形の数ではない）。

内部に頂点を追加する三角形分割は頂点の凸包における多角形の三角形分割である。ドロネー図は点を用いて三角形分割する別の手法である。

多角形の三角形被覆問題は、重複を許す条件での三角形で多角形を被覆する問題である。また、無限平面を多角形で敷き詰める、平面充填問題も関連する。