「重み最小三角形分割」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【おもみさいしょうさんかくけいぶんかつ (minimum-weight triangulation)】''' 三角形分割の辺長の総和を最小にするものを, 重み最小三...') |
|||
| 1行目: | 1行目: | ||
'''【おもみさいしょうさんかくけいぶんかつ (minimum-weight triangulation)】''' | '''【おもみさいしょうさんかくけいぶんかつ (minimum-weight triangulation)】''' | ||
| − | 三角形分割の辺長の総和を最小にするものを, 重み最小三角形分割と呼ぶ. この問題の計算量クラスについてはまだよくわかっていない. 2次元の場合実用的に大規模な問題が解けるLMT--スケルトン法などが知られている. 点集合が凸 | + | 三角形分割の辺長の総和を最小にするものを, 重み最小三角形分割と呼ぶ. この問題の計算量クラスについてはまだよくわかっていない. 2次元の場合実用的に大規模な問題が解けるLMT--スケルトン法などが知られている. 点集合が凸 <math>n \,</math>角形の頂点集合の場合, 重み最小問題は動的計画法によって<math>{\rm O}(n^3) \,</math>時間で解ける. 整数計画によるアプローチもある. |
2007年7月11日 (水) 16:47時点における版
【おもみさいしょうさんかくけいぶんかつ (minimum-weight triangulation)】
三角形分割の辺長の総和を最小にするものを, 重み最小三角形分割と呼ぶ. この問題の計算量クラスについてはまだよくわかっていない. 2次元の場合実用的に大規模な問題が解けるLMT--スケルトン法などが知られている. 点集合が凸 角形の頂点集合の場合, 重み最小問題は動的計画法によって時間で解ける. 整数計画によるアプローチもある.
