周期グラフとは単一の有限グラフをZd格子上に無限個並べ,各頂点を規則正しくつなぐことによって得られる無限グラフである.周期グラフは結晶格子,一様漸化式,VLSI回路など様々なもののモデルとして,その基礎的なグラフ理論的性質が結晶学及び計算機科学の分野で調べられてきた.本論文では,距離埋め込みによるグラフ上高速幾何アルゴリズム設計において周期グラフが距離空間とグラフとの橋渡しをすることが期待できること,及び近年のナノテクノロジの発展により浮上した平面的周期グラフ上の原子再配置問題において高速幾何アルゴリズムが有効であるということを動機として,周期グラフ上の幾何を解析する問題を扱う.

周期グラフ上の幾何は結晶学の観点からも重要な問題であり,数学的手法により解析がなされているが,結果は近似を与えるに留まっており,幾何厳密アルゴリズムを得るのに直接使うことはできない.我々は,計算機代数,離散幾何及び周期グラフにおける議論を活用し,周期グラフ上距離関数を計算する手法を与える.これにより,周期グラフ上の幾何を正確に解析することが可能となる.距離埋め込み理論からの動機及びナノテクノロジからの動機にから,我々は特に平面的周期グラフ及びl1埋め込み可能周期グラフの幾何がもつ凸性を明らかにし,実際に平面上の高速な計算幾何的アルゴリズムが周期グラフに適用可能であることも示す.

具体的には,まずHofting,Wankeらにより最短路問題が整数計画問題として定式化されていることに着目し,この整数計画問題の解析による距離解析を行う.コヒーレンスという組合せ的性質を定義し,コヒーレントな周期グラフ上では距離が整数線形計画問題により計算できることを示す.コヒーレンスは種々の結晶格子が満たすような性質である.さらに,距離関数計算に必要となる整数線形計画問題をパラメタ化したパラメトリック整数計画問題のための計算代数的アルゴリズムを提案する.コンパイラ最適化などへの応用からパラメトリック整数計画問題アルゴリズムは多く研究されているが,その出力は必ずしも最小ではない.本論文では,これまでのアルゴリズムとは異なる,トーリックイデアルの標準対分解を用いた計算代数的アルゴリズムを提案し,標準対分解の持つ幾何的性質により,このアルゴリズムが理論的に最小の解を出力することを示す.これにより解の幾何の解析が可能となる.さらに,標準対分解ための論理式双対化アルゴリズムによる高速実装を提案し,計算機実験により,従来実装が苦手としていたパラメタの個数が多い場合のパラメトリック整数計画問題で,我々のアルゴリズムが高速である場合があることを示す.また,トーリックイデアルの理論を用いて平面的周期グラフの単模性を示すことで,コヒーレントな平面的周期グラフ上では最短路問題が本質的に簡単になり,一般にNP困難である最短路問題に対して,強多項式時間アルゴリズムが可能となることを示す.

続いて,l1埋め込みを実際に計算することによる距離解析を行う.Chepoi, Deza, Grishukhinらによって提案された平面グラフのためのl1埋め込みアルゴリズムは無限グラフにも適用可能であるが,一般の周期グラフへの拡張は難しい.本論文ではEonによって結晶の対称性に関する不変量として提案された測地線束を用いた,一般の周期グラフのためのl1埋め込みアルゴリズムを提案する.

最後に,原子再配置問題のための高速アルゴリズムを考える.Calinescu, Dumitrescu, Pachらの結果から,この問題は最小重み二部マッチング問題と動作計画問題とに分かれることが分かっている.まず上でのグラフ上距離に関する結果を用い,平面上の計算幾何アルゴリズムにより周期グラフ上のボロノイ図が高速に計算できることを示すことで,Vaidyaによる最小重み二部マッチングのための幾何アルゴリズムを利用可能とする.グラフ上のボロノイ図としては,組合せ的なアルゴリズムにより算出されるErwigのグラフボロノイ図や,正方格子上の幾何に着目した幾何アルゴリズムにより算出されるデジタルボロノイ図があるが,本論文で提案するアルゴリズムはこれらとは全く異なる新しいアプローチによるものである.また,測地線束による最短路の定数サイズ表現を用いた,動作計画問題のための高速アルゴリズムを与える.具体的に,Chaveyが列挙したタイリングのうち,Deza, Grishukhin, Shtogrinらによってl1埋め込み可能であると示されたものを調べることで,多くの結晶構造でこの定数サイズ表現が可能であることも示す.

本論文は、周期グラフとよばれる無限構造の幾何学的性質を計算科学とアルゴリズムの理論的見地から研究を行ったものである。周期グラフは、同一の有限サイズのグラフを与えられた次元の格子上に無限個並べて規則正しくつなげることによって得られる基礎的な幾何的無限構造を有限サイズで表現したものであり、結晶学、ナノテクノロジー、VLSI回路解析、コンパイラ言語解析等様々な分野において重要な役割を持つ。しかしながら、その理論基盤はまだ整備されているとはいえず、周期グラフの性質を明らかにするとともにそれを扱うアルゴリズムの基礎を整備・発展させることができれば、それらの多くの応用の大きな発展が期待される。本論文では、特にナノテクノロジーにおける原子配置問題等にも応用可能な基礎的構造である、平面埋め込み可能な周期グラフに対して、これまで研究されていなかった周期グラフのクラスなどの性質を明らかにするとともに、距離関数の高速計算手法を提案し、実際の原子配置問題の解法についても新たな高速アルゴリズムを提案している。

本論文は八章からなり、第一章では、周期グラフの幾何的埋め込みとその関連問題に関するバックグラウンドについて議論し、本論文の研究の必要性ならびにその貢献について述べている。第二章では、本論文全般の準備として、本論文で用いられる周期グラフに関する定義、既知の性質、知られている関連アルゴリズムを紹介している。第三章では、平面周期グラフおよびL1埋め込み可能な周期グラフの持つ凸性の性質を明らかにし、それを利用したL1埋め込みアルゴリズムを提案している。さらに第四章においては、原子配置問題等においても重要である周期グラフ上の最短路問題を扱っている。この章においては、多くの結晶構造が満たしており、応用範囲の広い性質であるコヒーレンスという新しい性質を定義し、その性質を持つ周期グラフのクラスに対して、距離関数が整数計画問題を用いて高速に計算することができることを示している。第六章においては、さらに、パラメトリックな問題に対しても、トーリックイデアルの標準対分解を用いた新しい計算代数的アルゴリズムを提案し、計算機実験を通して、それが有効であることを示している。さらに第六章においては、実際の応用として原子配置問題における複数原子の移動パスを求める問題で必要とされる周期グラフ上の近傍検索および二部グラフマッチングの問題の新たな高速解法を提案している。さらに第七章では、第六章の結果を用いて、実際の原子配置問題における移動計画問題の解法を提案している。最後に第八章では、本論文の研究の総括ならびに今後の展望について議論を行っている。

このように、本論文は、多くの応用のある周期グラフという幾何的対象に対し、計算代数、計算幾何、アルゴリズムの各方面から理論の整備と実際の応用への解決策を提供し、計算科学のみならず、多くの応用分野に対して大きな貢献を行っている。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。