重み最小三角形分割

【おもみさいしょうさんかくけいぶんかつ (minimum-weight triangulation)】

三角形分割の辺長の総和を最小にするものを, 重み最小三角形分割と呼ぶ. この問題の計算量クラスについてはまだよくわかっていない. 2次元の場合実用的に大規模な問題が解けるLMT--スケルトン法などが知られている. 点集合が凸$n$角形の頂点集合の場合, 重み最小問題は動的計画法によって${\rm O}(n^3)$時間で解ける. 整数計画によるアプローチもある.