多角形の三角形分割
長きに渡って、単純多角形を O ( n log  n ) {\displaystyle O(n\log n)} 時間より高速な三角形分割アルゴリズムが未発見であった。その後、Tarjan & Van Wyk (1988)は O ( n log  log  n ) {\displaystyle O(n\log \log n)} 時間で三角化を行うアルゴリズムを発見し、後にKirkpatrick Klaweとロバート・タージャンにより簡単化された。複数の改善により、 O ( n log ∗  n ) {\displaystyle O(n\log ^{\ast }n)} (実用上ほぼ線形時間)を実現している。
1991年にバーナード・チャゼルは非常な複雑なアルゴリズムではあるが、任意の単純多角形を線形時間で三角形分割するアルゴリズムを示した。また、乱択アルゴリズムを用いることで、平均計算時間が線形時間であるアルゴリズムも存在する。
ザイデルの分割アルゴリズムとチャゼルの三角形分割については、 Li & Klette (2011) が詳しい。
穴を持つn頂点の多角形の三角形分割の時間計算量の下界は Ω ( n log  n ) {\displaystyle \Omega (n\log n)} 与えられている。
最小重み三角形分割は辺の長さの和が最小となるような三角形分割を求める問題である(三角形の数ではない)。
内部に頂点を追加する三角形分割は頂点の凸包における多角形の三角形分割である。ドロネー図は点を用いて三角形分割する別の手法である。
多角形の三角形被覆問題は、重複を許す条件での三角形で多角形を被覆する問題である。また、無限平面を多角形で敷き詰める、平面充填問題も関連する。