計算幾何学とよばれる研究分野が,アルゴリズム論から研究対象を幾何的アルゴリズムに限定して意識的に抽出されたのは,1978年のM.I.Shamosの博士論文からであるといわれる.その後,計算幾何学の研究は急速に進展し,数多くの効率的な幾何的アルゴリズムが開発された.幾何的な問題の解析も進み,多くの幾何的な問題でアルゴリズムの計算量,記憶量の限界が明らかになり,また,そこまで効率化が達成された幾何的アルゴリズムも少なくない.また,幾何的アルゴリズムに対する実用上の需要も多い.

　具体的に,5章で構成法を述べた各種Voronoi図を例にする.平面上に有限個の点を与えたとき,それらの点による平面の勢力圏分割を表す図をVoronoi図という.Voronoi図とその各種の拡張の構成は埋論的な興味に加え,実用面からの要求も強く,効率的なアルゴリズムの実装が求められている.

　実用上の需要に応じるため,Voronoi図の構成に限らず,多くの幾何的な問題に対して,効率的な幾何的アルゴリズムの開発とその実装が求められている.しかしながら,理論的には効率的なアルゴリズムが,実装すると実用に堪えないものであることが少なくない.実用程度の入力データ量では高速性を発揮できない場合は論外としても,実用上も効率的と思われる幾何的アルゴリズムでも,素直に実装すると,データ破壊,異常終了,無限ループなどを引き起こす.

　このような状況を反省し,近年になって,計算幾何学では,この原因と対策に関する研究が積極的に進められるようになった.本論文では,計算幾何学で開発されてきた効率的なはずのアルゴリズムが,多くの場合実用にならないという問題点を指摘し,その原因である計算誤差と退化に関する研究を行なった.

　計算機の計算精度は有限である.これはふたつの意味をもつ.すなわち,第1の意味は,理論的な面から、計算機に有限の記憶量しか与えられていない以上,計算できる対象は有限個に限られ,アルゴリズム設計者が想定しているすべての場合を扱うには無理があるということである.第2の意味は,実用面から,任意の実数データを浮動小数形式で受け入れ,計算誤差付きで処理しなければ,計算速度と既存システムとの整合性の点から,実用性を欠くということである.

　しかしながら,従来,アルゴリズムの理論展開や設計時には無限精度の計算が仮定されることが多い.そうして,実数値の入力が無限精度で加工できることになると,次は,判定式が0になる場合を"滅多にないこと"として無視できるようになる.このため,計算精度の有限性から生じる計算誤差と退化の問題は,実用時まで放置されることになる.

　本論文では,まずはじめに1章で,このような計算誤差と退化の問題に言及し,幾何的アルゴリズムの設計の段階では効率的で優秀なアルゴリズムが,実装,実用の段階では数値的安定性を欠き意味をなさない場合が少なくないことを指摘した.

　次に2章で,計算幾何学での既存の研究をふまえて,幾何的アルゴリズムで扱うデータを位相データと計量データに分け,退化を計量データを変数とする判定式の零点として定義した.また,判定式から除算と開平を消去し,判定式を多項式に限定できることも示した.この退化の定義により,入力を定数ビット以下に制限すれば,無誤差計算が有限精度でもできることを示した.その結果,退化を代数的に扱う枠組みが提示可能になった.

　次に3章で,代数的に退化を扱う枠組みにおける退化対処法を,代数的退化対処法と名付けた.次に,Yap,Edelsbrunnerら,Emirisら,Fortuneによる,既存の退化対処法を整理し,前節の枠組みのなかで,項順序による多項式環の順序環化,記号的無限小摂動による零点の解消という手法として,統一的な解釈を行なった.退化対処法の簡潔さと適用範囲は裏腹の関係にあり,Yapの方法が最も適用範囲が広く,Edelsbrunnerら,Emirisら,Fortuneと続くが,簡潔さでは,Fortuneが最も優れ,Emirisら,Edelsbrunnerら,Yapと続く.適用する場面に応じて使うべき方法は別れる.続いて,超準解析の手法を用いて,無限小摂動の解釈を行ない,整数論と集合論を基礎におく数学構造から幾何的アルゴリズムを構成する限り,代数的退化対処法は本質的に記号的無限小摂動法以外にないことを示し,代数的退化対処法のある種の限界を示した.続いて,Grobner基底を利用して,新しい退化対処法を考案した.既存の方法が,前処理として実質的に判定多項式の微分式を計算し,幾何的アルゴリズムを書き換える方式なのに対し,この方法は,アルゴリズムの実行中に判定多項式の微分式に相当するものを計算していく方式をとる.この方式は非退化時にも余分な計算が必要な点が欠点であるが,適用範囲が広く簡潔なため実装が楽で,既に実装されている幾何的プログラムを気楽に退化対処版にしたい場合には有利である.

　次に4章で,剰余演算を利用した無誤差計算について取り上げた.代数的退化対処法は,高精度の無誤差計算を前提にする.無誤差計算に関しては,理論的には計算桁数を十分に多くとれば達成できる.しかし,実用の観点からは,長すぎる桁数の計算は計算時間の増大を引き起こしてしまう.本章では,必要十分な桁数を求めることの困難を指摘した.さらに,必要な計算結果は値ではなく符号であることに着目して,剰余演算を用いて長い桁数の数の加減乗算の高速化し,計算して得られた剰余から,値を復元することなく符号を復元する方法を提案した.さらに,予備的な計算機実験を行ない,実際の効果を確認した.

　次に5章で,もう一つの退化対処法である位相優先法の解説と,位相優先法に基づく幾何的アルゴリズムの開発を行なった.位相優先法は計算誤差の存在を前提にする方法であり,退化の有無を厳密に判定することなく自然に退化を回避する.問題によって保持すべき位相構造が異なるので,概論的な方法論だけではすぐに利用するというわけにはいかず,実際に役に立つアルゴリズムを構築するためには,具体的な事例ごとの工夫が必要である.本章では,位相優先法の具体例として,新規に開発した線分Voronoi図と多角形Voronoi図の構成アルゴリズムをその実装プログラムを中心に解説した.そのために必要な(点)Voronoi図の構成アルゴリズムに関しても概説した.また,実装した線分Voronoi図,多角形Voronoi図の構成プログラムSEGVOR,PLVORに関しては,各種の計算機実験を行ない,数値的安定性を実証し,また,実用に足りる計算速度を確保していることを示した.

　まとめとして6章で,研究を振り返り,総合的に代数的退化対処法と位相優先法を比較し,基本的な性格を指摘した.代数的退化対処法は,本質的に計算時間が余計にかかるが,出力の位相データは,必ずある非退化入力によって実現できるものになる.一方,位相優先法は,位相データの持つべき性質のうち判定式の符号決定のために浮動小数計算ができるため,計算時間の点では絶対に有利である.代数的退化対処法と位相優先法のどちらも,実用上の改良を加えることができるが,基本的性格からくる困難を除くには至らないことも指摘した.退化や計算誤差への考慮のない,または対処法として不十分なプログラムが通用している現状と比較して,代数的退化対処法と位相優先法のどちらも,プログラマの退化に対処するための労力をなくし,プログラム本体の開発に労力を集中させることができる点と,理論的に効率がよい幾何的アルゴリズムを実際にも利用できるという点で,格段に優れていると結論付けた.加えて,本論文の研究で,線分Voronoi図,多角形Voronoi図を溝成するプログラムSEGVOR,PLVORが具体的なソフトウェアとして得られたことは,理論展開とは別に、それ自体が成果である.最後に、今後の課題として,従来の幾何的アルゴリズムの退化研究が採用している,判定式の値が0になるときのすべてが退化であるという前提に対して,対処すべき退化を分離する可能性を指摘した.

　幾何学的な情報の処理は,地理情報処理,コンピュータグラフィクスなど多くの応用をもつ工学的に重要な技術で,その研究は計算幾何学とよばれる分野で近年精力的に進んでいる.しかし,そこで得られている幾何アルゴリズムは無限に高い精度で計算ができるという前提のもとで正しさが保証されているにすぎず,有限の精度しかもたない現実の計算機で必ずしも安定に動作するものではない.この理論と現実の間に横たわる大きな溝を埋めることは,工学的に重要かつ緊急の課題である.

　本論文は,この課題に取り組み,いくつかの局面での解決策を提案したもので,「有限の計算精度のもとでの幾何的アルゴリズムの研究」と題して,6章より成る.

　第1章「はじめに」では,本研究の背景を論じ,本論文の位置付けを行なっている.

　第2章「幾何的アルゴリズムと退化」では,計算幾何学の歴史をまとめるとともに,従来のアルゴリズムの体系が現実の計算機の上でかならずしも理論どおりの性能を発揮しない原因が退化と計算精度の有限性にあることを詳しく論じている.そしてこの議論を通して,本論文で扱うべき研究課題とその工学的意義を明確にしている.

　第3章は「代数的退化対処法」と題し,アルゴリズムの数値的不安定性の原因の一つである退化を解消する方法を論じている.まず,今までに提案されている記号摂動の諸手法を紹介し,超準解析の枠組からそれら相互の関係を明確化し体系化している.また,この枠組では,今までに提案されているもの以外の退化解消法は存在しないことも証明されている.さらに今までの方法が,入力データの全貌がわかってから対策を施すといういわばコンパイル方式なのに対して,入力データが逐次与えられる環境で全貌を知る以前に施すことのできるインタプリタ方式の新しい方法を,グレブナ基底理論に基づいて構成している.

　第4章「剰余演算を利用した多項式の値の符号判定法」では,多項式の変数に数値を代入したときの多項式の値の符号を,剰余演算を用いることによって単精度の計算のみで厳密に求める方法を提案している.幾何的アルゴリズムの中での位相構造の判定は,一般にある多項式に入力データを代入して得られる値の符号に基づいてなされる.この符号を厳密に求めるために,通常は多倍長の精度で計算を行なわなければならない.しかし,これは計算時間を要するため,アルゴリズムの効率を圧迫する原因となっている.本論文では,ここで必要なのは値自身ではなくその符号であることに着目し,剰余演算の代数的性質を巧妙に利用して低い精度の計算で符号を厳密に求める方法をいくつか考案している.これによれば,符号の判定を単精度の計算のみによって行なうことができるので,アルゴリズムの効率を著しく向上させることができる.この方法の有効性を計算実験によっても実証している.

　以上の第3章,第4章では,幾何的対象の位相構造を常に正しく判定するために十分な計算精度を確保するという方針でアルゴリズムの安定化をめざす際に生じる諸問題に取り組んでいる.一方,数値計算は通常の浮動小数点方式で行ない,そこで生じる誤差がアルゴリズムに与える影響を最小限に止めることによって安定化を図ることもできる.この方針を採用したのが次の第5章である.

　第5章は「位相優先法」と題し,幾何的対象がもつべき位相的性質の一貫性を数値計算結果より優先度の高い情報として利用することによる安定化技術を論じている.まず,平面を写えられた点の勢力圏に分割するボロノイ図を例にとり上げて,位相的性質の優先的利用によって安定化がもたらされる原理を述べ,これを位相優先法と名付けている.次にこれを線分の勢力圏図,多角形の勢力圏図の構成法へと一般化し,それぞれの場合に生じる数値誤差の影響を最小限にくい止めるための精密な議論を展開して対策を講じている.さらにここに提案する対策を計算機プログラムとして実装し,どれほど条件の悪い入力データに対しても暴走することなく,必ず処理が最後まで進んで位相的に無矛盾な結果を出力することを,多くの計算実験によっても確認している.

　第6章「まとめ」では本論文の主要な成果とその実用的意義をまとめるとともに,今後に残された課題について論じている.

　以上を要するに,本論文は,理論家の提供する幾何的アルゴリズムが,数値計算を有限の精度でしか実行できない現実の計算環境では不安定なものであることを直視し,その安定化のための汎用的かつ根本的解決策を与えたもので,数理工学の発展に大きく貢献するものである.よって博士(工学)の学位論文として合格と認める.