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