非線形幾何手法による幾何的最適化問題におけるアルゴリズムの研究開発

これまで、計算幾何学においては静止している対称物に対し、それを直線で近似して問題を解くということが多かった。しかし、近年の各種の応用から対象物を曲線で近似し、さらにそれらが時間と共に動いている場合を考える必要性に迫られている。このように非線形で動的な問題が重要視されてきているが、動的対象物に対する非線形な取り組みは始められたばかりで、研究成果も少ないし、実用上有効であるとはまだいえない。そこで、本研究では、計算幾何学の分野における非線形問題に対する手法を用いて、各種の幾何的最適化問題に対して、動的対象物への非線形な拡張を考え、その実用的で有効な算法を開発する試みを行ってきた。具体的には、まず、コンピュータ・グラフィックス、モーションプランニングなどにおける実用的な場面に現れる動的非線形問題を調査、分類し、その結果、計算幾何学の重要な概念として多くの問題に利用できるVoronoi図やアレンジメントなどがこのような問題における動的対称物に対しても有効であることをわかったので、これらの概念を動的対称物に拡張する作業を行った。特にVoronoi図に関しては動的な対称物に関して、高次のVoronoi図に関する研究を行った。Voronoi図を用いて効率良く解ける問題が多く存在することから、ここで得られた高次の動的Voronoiもそれらの問題の動的な場面で有用である。アレンジメントに関する研究は継続中であるが、移動通信などの施設配置問題など多くの問題に対しても応用できると考えられる。また、本研究まで得られた成果に関しては学術論文や研究資料などで発表し、研究成果の公表を行った。

これまで、計算幾何学においては静止している対称物に対し、それを直線で近似して問題を解くということが多かった。しかし、近年の各種の応用から対象物を曲線で近似し、さらにそれらが時間と共に動いている場合を考える必要性に迫られている。このように非線形で動的な問題が重要視されてきているが、動的対象物に対する非線形な取り組みは始められたばかりで、研究成果も少ないし、実用上有効であるとはまだいえない。そこで、本研究では、計算幾何学の分野における非線形問題に対する手法を用いて、各種の幾何的最適化問題に対して、動的対象物への非線形な拡張を考え、その実用的で有効な算法を開発する試みを行ってきた。具体的には、まず、コンピュータ・グラフィックス、モーションプランニングなどにおける実用的な場面に現れる動的非線形問題を調査、分類し、その結果、計算幾何学の重要な概念として多くの問題に利用できるVoronoi図やアレンジメントなどがこのような問題における動的対称物に対しても有効であることをわかったので、これらの概念を動的対称物に拡張する作業を行った。特にVoronoi図に関しては動的な対称物に関して、高次のVoronoi図に関する研究を行った。Voronoi図を用いて効率良く解ける問題が多く存在することから、ここで得られた高次の動的Voronoiもそれらの問題の動的な場面で有用である。アレンジメントに関する研究は継続中であるが、移動通信などの施設配置問題など多くの問題に対しても応用できると考えられる。また、本研究まで得られた成果に関しては学術論文や研究資料などで発表し、研究成果の公表を行った。