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