本論文は6章から成り、第1章では三角形分割の問題点とくに3次元での困難を提示し、第2章では三角形分割が整数計画問題として定式化できることを述べ、第3章では問題のサイズと計算量の関係、三角形分割の最適性を計算例に基づいて提示し、第4章では整数計画問題として扱うのに困難な事例を扱う方法を提案し、第5章では応用として辺長和最小三角形分割、(準)正多面体、ダイセクション、データ依存三角形分割、四角形(六面体)分割などについて議論し、第6章では結論について述べている。 点集合の凸包の三角形分割については、様々な見地から多くの研究がなされている。高次元での三角形分割については、2次元の場合とかなり特性が異なることがわかってきており、既存研究の多くは2次元に特化したものである。 三角形分割の最適性に関しては、従来計算幾何学によるアプローチが主流であった。最小角などボトルネックとなる値は三角形分割の品質を保証する上で重要な尺度であり、計算幾何学の分野で研究が重ねられているが、2次元に比べ、3次元ではあまり結果が得られていない。例えば、2次元においてはDelaunay三角形分割が多くの最適性を満たしているが、3次元ではほとんど成り立たない。 一方で、三角形分割には有限要素法やコンピューターグラフィックスなどの現実的な応用があり、近年の計算機能力の向上とあいまって、より高次元、特に3次元での三角形分割に関する技術や知見が求められている。このように、三角形分割の最適化、特に3次元のケースは、理論上、応用上共に重要であると同時に、計算幾何学的アプローチのみではカバーしきれない分野である。 本論文では、最適化の手法として整数計画法をとりあげ、この見地から三角形分割の最適性を考察した。手法自体は次元に依存しないが、3次元に主に着目する。これは、2次元と3次元以上の三角形分割の間には難度に大きな隔たりがあり、その向こう側では3次元が最も扱いやすく、また様々な応用が存在するためである。さらに、計算機実験を通して、整数計画問題としての分析を行った。 はじめに定式化を検証した。三角形分割の最適化に関しては幾つか独立して既存研究があるが、提出者はこれらを一般化した上で(1)安定集合問題、(2)集合分割問題のそれぞれに還元される二つのグループに分類し、比較検討した。 次に、定式化に関する考察に基づき行った予備実験の結果を検証した。実際的な問題点の一つは、解ける問題の規模が小さいことである。もう一つの問題点は、線形緩和解が非常に細かな小数解となる場合があることで、計算幾何でしばしば取り上げられるボトルネック値の最適化や、数学的に興味深い重み無しの目的関数を採用したときに起こる。そこで、提出者はこれらに対処するため整数計画問題として分析した上で、整数計画の手法を応用した。より大規模の問題を解くために列生成法を適用し、数理計画問題としての退化や、双対の幾何的な意味合いについてもあわせて議論した。ボトルネックの最適化には二分探索法を適用した。重み無しの目的関数には、三角形分割の幾何的な特性に着目した二種類の新たな切除平面を導入し、既存のclique,odd-cycleといった切除平面が現実的には意味を成さないのに対し、新たな二種類の切除平面が効果的であることを計算機実験により実証した。こうした切除平面を導入しても依然として分枝限定法は必要であり、低次元の単体に対応する変数を導入することで分枝限定法を効率化する手法も示した。 最後に、整数計画を用いた三角形分割の応用や拡張を、理論上あるいは実用上興味深い2、3次元において検討した。それぞれについて最適解を与えることにより、新たな知見が得られた。最適化した三角形分割の素直な適用として、辺長和最小三角形分割とデータ依存三角形分割を取り上げ、点集合の退化と対称性についての議論の材料として(準)正多面体に着目し、最小/最大四面体数を与えた。ダイセクションは三角形分割を若干拡張した概念であり点配置の退化と大きな関わりがあるが、これについても定式化の拡張を中心に検討した。産業への応用上非常に重要な2次元での四角形分割、および3次元での六面体分割を想定し、定式化の拡張とともに計算機実験を行った。 論文提出者は、理論のみでなく計算機実験による検証を行い、実装および実験結果についても詳細な分析を行った。特に、理論および応用での中規模の問題に対し、実際に様々な尺度のもと最適解を与えた。これらは既存の方法では求められなかったものであり、理論上の限界ではなく実際にどの程度解を改善できるかといった、問題および目的関数に関する新たな知見を得ることができた。 本研究は、今井浩との共同研究であるが、論文提出者が主体となって分析及び検証を行ったもので、論文提出者の寄与が十分であると判断する。 したがって、博士(理学)の学位を授与できると認める。 |