辺長和最小三角形分割に対する分枝切除法
スポンサーリンク
概要
- 論文の詳細を見る
点集合の3角形分割はコンピューターグラフィクス・CAD・数値計算の分野で有用な基本的データ構造であり, 計算幾何学では他の問題を解くための有効な道具ともなる。平面上のn点の3角形分割については, 最小角を最大にするなどの意味でできるだけ各3角形が正3角形に近いように分割する Delanay 3角形分割が有名で, 現在では計算幾何の代表的成果として計算誤差にも強いプログラムも広く存在する. 一方, 辺長和最小の3角形分割については, 以前その計算量クラスが不明で, 近年, 辺長和最小分割に含なれる辺部分集合(骨格という)の研究が盛んになされ, 正方形内に一様分布している実用的サイズの点集合に対してはかなり良好な成果を上げている. 本稿では, 辺長和最小3角形分割を辺の交グラフの最小重み極大独立点集合問題としてとらえ, 組合せ最適化で近年幅広い成果を上げている分枝切除法の適用について調べる. まず, 骨格に関する研究のうちβ骨格を利用することにより, 予め変数の数をかなり削減することができ, 次にグラフの独立点集合に対する典型的な切除平面の他に平面幾何から誘導される切除平面を考え, 全体として幾何の条件を活用した組合せ最適化アルゴリズムを構築する. 計算機実験を行ない, その結果100点の点集合に対しては実用的な時間内に求めることできた. この方法は, さらに骨格に関する最近のよりよい成果や分枝切除での内点法の利用などによる効率化を図ることにより, さらに大規模の問題を解くことができると思われる.
- 1996-07-26
論文 | ランダム
- 8. 消化性潰瘍手術症例の年次的検討 : 十二指腸潰瘍穿孔例に対する迷切術を中心に(第20回胃外科研究会)
- 358 新しいマーカーによる食道癌術後凝固線溶状態の検討(第38回日本消化器外科学会総会)
- 355 肥満患者における食道癌周術期病態の特殊性 : 呼吸管理上の問題について(第38回日本消化器外科学会総会)
- 64 胃全摘, 噴門側胃切除術後再建における器械吻合の臨床的検討(第38回日本消化器外科学会総会)
- P7-5 肋骨弓吊り上げ・経腹的横隔膜切開による非開胸での食道浸潤胃癌の手術, その方法と術後生存率および再発形式からみた妥当性(第38回日本消化器外科学会総会)