On the geometry on the periodic graphs: analysis by computation of the graph-metric and application to fast geometric algorithms


(邦訳:周期グラフ上の幾何について:グラフ距離関数計算による解析及び高速幾何アルゴリズムへの応用)

 
夫 紀恵
国立情報学研究所 特任研究員

[背景]ナノテクノロジの発展による結晶表面上再配置問題の浮上
[問題]結晶の持つ数理構造を利用した高速アルゴリズム開発
[貢献]離散幾何・計算代数・計算幾何分野への理論貢献


 近年,大阪大学の森田,阿部,杉本らにより,結晶表面上の原子を原子間力顕微鏡を用いて1つずつ動かすことで,常温環境下で所望の原子配置を作り出す技術が開発され(論文(http://www.nature.com/nmat/journal/v4/n2/abs/nmat1297.html)及び補助資料のビデオ(http://www.nature.com/nmat/journal/v4/n2/extref/nmat1297-s3.mov)),次世代の原子メモリ・量子デバイスを実現するための有力な候補の1つとして注目を浴びている.この技術の自動的かつ効率的な運用のためには,所望の原子配置を最小の手間で達成するための動作計画を求めるアルゴリズムが不可欠である.

 本研究では,このような動機に触発され,動作計画問題を周期グラフ上でのスライドパズルのような再配置問題(図1)としてモデル化し,アルゴリズム論を展開した.周期グラフとは繰り返し構造を持つ無限グラフであり,一周期分のみを取り出した静的グラフと呼ばれる有限のデータ構造で記述される.周期グラフは一様漸化式,VLSI回路,結晶など,さまざまなもののモデルとして古くから研究がなされており,通常の有限グラフでは容易な問題が,周期グラフ上では困難になることがあるという事が分かっている.再配置問題で本質的に重要となる最短路問題もそのような問題のうちの1つである.

 


 周期グラフ上のある二点が与えられた時にその二点間の最短路長を定数時間で返すような関数を最短路関数と呼ぶ.結晶表面に対応するような多くの周期グラフが,l1距離埋め込み可能性や平面性など,一般の周期グラフが持つとは限らないよい構造を持つクラスに含まれることが知られている.本研究ではこうした周期グラフのクラスで最短路関数計算アルゴリズムを開発し,その結果を用いて周期グラフの幾何構造を解明・再配置問題のための高速計算幾何アルゴリズムの開発を行った.この過程において浮上してきたさまざまな分野における新たな理論的問題を解決し,以下のように各分野への貢献を行った.

(1)離散幾何
    グラフのl1埋め込みは離散幾何分野の重要問題であり,これを計算することでグラフ上の最短路関数を計算することができる.本研究では一般の周期グラフのl1埋め込みアルゴリズムを与えた.

(2)グラフ理論
    11埋め込み可能な周期グラフの持つ性質を抽出した“コヒーレント”というより一般的な組合せ的性質を提案し,コヒーレントな周期グラフの最短路関数がパラメトリック整数計画により計算できることを示した.さらに計算代数的手法により平面的周期グラフの持つ性質を明らかにすることで,コヒーレントかつ平面的周期グラフ上での強多項式時間最短路計算アルゴリズムも開発した.

(3)計算代数
    パラメトリック整数計画は多くの応用を持つ重要問題である.実際に最短路関数を計算するという観点から,離散数学における重要問題である論理関数双対化アルゴリズムを用いた計算代数アルゴリズムの改良を提案し,従来アルゴリズムより高速にパラメタの多数あるパラメトリック整数計画を解くことができることができることを示した.

 周期グラフ上の最短路関数を計算するという問題を通し,これまで個別に取り扱われてきた各分野の重要概念を結びつけることができた.今後,この新たな視点からさらにパラメトリック整数計画等の理論を推し進めることができると期待している.
 
 (2013年6月14日受付)
取得年月日:2013年3月
学位種別:博士(情報理工学)
大学:東京大学



推薦文
:(アルゴリズム研究会)


動画“A Boy And His Atom: The World's Smallest Movie”のように原子を望み通りに移動させることは難問である.これは本問題を理論計算機科学の視点から周期グラフ上の問題として定式化し,計算幾何学,組合せ最適化,計算機代数,論理関数を総動員して効率的算法を設計した研究である.その一部はISAAC'12最優秀学生論文賞に輝いた.


著者からの一言


周期グラフを研究する人が周囲におらず研究が手探りであった一方で,さまざまな分野の観点から非常に自由に研究させていただけて楽しかったです.今後はこれまでのような数理面の研究のみでなく,実際に早いアルゴリズム開発などにもどんどん取り組んでいきたいと考えています.