三角形分割の最適性と整数計画による定式化

• Item type: Journal(1)
• 公開日: 1999-07-15
• タイトル: 三角形分割の最適性と整数計画による定式化
• タイトル / 言語: en
• タイトル: Optimality and Integer Programming Formulations of Triangulations
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: アルゴリズム理論
• 著者所属: 日本アイ・ビー・エム株式会社東京基礎研究所／東京大学理学部情報科学科
• 著者所属: 東京大学理学部情報科学科
• 著者所属(英): en
• 著者所属(英): Tokyo Research Laboratory, IBM Research/Department of Information Science, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Information Science, University of Tokyo
• 著者名: 田島, 玲; 今井, 浩
• 著者名(英): Akira, Tajima; Hiroshi, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 二次元における三角形分割については多くの研究がなされてきているが FEMをはじめ応用上も重要である三次元での三角形分割については 平坦さ 角度 三角形分割の要素数をはじめとする様々な性質はあまり知られていない.本論文では 三次元となることで三角形分割の特性 最適性にどのような違いが出てくるかを紹介し 整数計画法を用いた実験を通してこれらを実証する.一般次元での三角形分割に対する整数計画法による定式化として 既存の関連研究を整理 また一部を拡張し 1)安定集合問題に基づく定式化 2)集合分割問題に基づく定式化の2種類としてとらえ 比較検討を行う.理論上/応用上興味深い最適化の目的関数に関する考察を加えるとともに これらに基づいた計算機実験の結果を示し 検証する.特に 二次元では万能と見られているDelaunay三角形分割が三次元では基準によっては最適値から大きく離れることが確認できた.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The properties of triangulations, and their differences between two and three dimensions, are computationally investigated by using integer programming (IP). Two IP formulations of triangulations are compared, one based on the stable set problem, and the other based on the set partitioning problem. Some properties that are interesting from a theoretical or practical point of view are considered as objective functions for IP. Finally, some computational results are given. By this approach, three-dimensional triangulations can now be treated in a flexible and efficient way, and interesting properties of three-dimensional triangulations have been newly found.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 40, 号 7, p. 2861-2871, 発行日 1999-07-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764