多角形の三角形分割
多角形の三角形分割アルゴリズムは多数提案されている。
多角形Pの三角形分割関連で有用なグラフに、三角形分割の双対グラフがある。Pの三角形分割TPが与えられたとき、TPの三角形を頂点として持ち隣接を辺として表すグラフG(TP)が定義できる。G(TP)は木であり、その最大次数は3である。
多角形の三角形分割(たかっけいのさんかっけいぶんかつ)は計算幾何学の分野で用いられる、(単連結な)多角形の領域Pの三角形の集合への分割である。つまり、和集合がPである互いに重なり合わない三角形の集合の発見法である。
三角形分割は平面直線グラフの特殊な場合としてみなせる。穴のない図形の頂点のみを用いた三角形分割は、外平面的グラフである。