多角形の三角形分割

多角形の三角形分割（たかっけいのさんかっけいぶんかつ）は計算幾何学の分野で用いられる、（単連結な）多角形の領域Pの三角形の集合への分割である^[1]。つまり、和集合がPである互いに重なり合わない三角形の集合の発見法である。

三角形分割は平面直線グラフの特殊な場合としてみなせる。穴のない図形の頂点のみを用いた三角形分割は、外平面的グラフである。

追加点を用いない多角形の三角形分割

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

特別な場合

凸七角形の42通りの三角形分割。この数字は5番目のカタラン数である。

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

レオンハルト・オイラーによって、凸n角形の三角形分割の組合せの数は、交差しない対角線の数であり、(n − 2)番目のカタラン数、つまり^[2]。

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

耳刈り取り法

多角形の「耳」

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

このアルゴリズムは実装が容易であるが他のアルゴリズムより遅く、穴を持たない多角形でしか動作しない。凸である頂点と凹である頂点を別のリストとして持つ実装の時間計算量はO(n²)である。この方法は耳刈り取り法もしくは耳取り除き法として知られるアルゴリズムで、Hossam ElGindy、Hazel Everett、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)}$与えられている。

関連する問題

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

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

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