重み最小三角形分割

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

三角形分割の辺長の総和を最小にするものを, 重み最小三角形分割と呼ぶ. この問題の計算量クラスについてはまだよくわかっていない. 2次元の場合実用的に大規模な問題が解けるLMT--スケルトン法などが知られている. 点集合が凸 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n \,} 角形の頂点集合の場合, 重み最小問題は動的計画法によって構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm O}(n^3) \,} 時間で解ける. 整数計画によるアプローチもある.