辺長和最小三角形分割に対する分枝切除法
スポンサーリンク
概要
- 論文の詳細を見る
点集合の3角形分割はコンピューターグラフィクス・CAD・数値計算の分野で有用な基本的データ構造であり, 計算幾何学では他の問題を解くための有効な道具ともなる。平面上のn点の3角形分割については, 最小角を最大にするなどの意味でできるだけ各3角形が正3角形に近いように分割する Delanay 3角形分割が有名で, 現在では計算幾何の代表的成果として計算誤差にも強いプログラムも広く存在する. 一方, 辺長和最小の3角形分割については, 以前その計算量クラスが不明で, 近年, 辺長和最小分割に含なれる辺部分集合(骨格という)の研究が盛んになされ, 正方形内に一様分布している実用的サイズの点集合に対してはかなり良好な成果を上げている. 本稿では, 辺長和最小3角形分割を辺の交グラフの最小重み極大独立点集合問題としてとらえ, 組合せ最適化で近年幅広い成果を上げている分枝切除法の適用について調べる. まず, 骨格に関する研究のうちβ骨格を利用することにより, 予め変数の数をかなり削減することができ, 次にグラフの独立点集合に対する典型的な切除平面の他に平面幾何から誘導される切除平面を考え, 全体として幾何の条件を活用した組合せ最適化アルゴリズムを構築する. 計算機実験を行ない, その結果100点の点集合に対しては実用的な時間内に求めることできた. この方法は, さらに骨格に関する最近のよりよい成果や分枝切除での内点法の利用などによる効率化を図ることにより, さらに大規模の問題を解くことができると思われる.
- 1996-07-26
論文 | ランダム
- 理学療法士の競技スポーツへのかかわりとその実際 : 水泳を中心に(教育セミナー,近未来に向けての理学療法〜理学療法アプローチの確立〜,第45回日本理学療法士協会全国学術研修大会)
- やる気を引き出す動作訓練(教育セミナー,近未来に向けての理学療法〜理学療法アプローチの確立〜,第45回日本理学療法士協会全国学術研修大会)
- 脳からみた動作分析(教育セミナー,近未来に向けての理学療法〜理学療法アプローチの確立〜,第45回日本理学療法士協会全国学術研修大会)
- 症例発表に向けて(新人教育セミナー,近未来に向けての理学療法〜理学療法アプローチの確立〜,第45回日本理学療法士協会全国学術研修大会)
- コミュニケーションスキル : コーチングを利用して(新人教育セミナー,近未来に向けての理学療法〜理学療法アプローチの確立〜,第45回日本理学療法士協会全国学術研修大会)