ボロノイ図は空間を指定された点の勢力圏に分割する図形で、種々の幾何データ解析によく使われる道具である。本論文では、このボロノイ図の構成算法、及び、ボロノイ図利用法の代表例である最近点探索の高速化に寄与するとともに、地理的探索、形状解析、ステレオロジーのための新しい応用技術を開拓する。

　まず、ボロノイ図を構成するための逐次添加型算法を入力点配置に応じて適応的に高速化するための指針を構成した。ボロノイ図構成算法をロバストに実装する代表的手法は整数帰着法であり、それを高速化するために「混合演算」という方針が使われている。本論文では、この混合演算を改良し、混合演算の枠組での新方式の提案を行ない、多様な入力点配置に対する性能を旧方式と比較する実験を通じて、与えられた入力点配置に適した方式を選択するための指針を得る。なお、ここで示される混合演算は、他の低次元幾何学問題を解く時にも適用可能である。

　また、「最近点探索問題」は大変基本的かつ重要な問題であり、ボロノイ図を利用して解く問題の代表例でもある。ただし、その効率化のためには木構造を併用する必要があり、その種の木構造にいくつかの種類があるので、やはり与えられた入力点配置に適した選択が求められる。ここでも、各木構造の性能を比較する実験を通じて、与えられた入力点配置に適した木構造を選択するための指針を得る。

　次に、「寄り道施設探索問題」という実用上現れそうな問題を新しく提案し、これがボロノイ図を利用して効率的に解けることを示す。ボロノイ図を使わずに木構造だけによる方法も含めて、実験を通じて性能を比較する。さらに、このボロノイ図を利用する解法をより広い範囲の「領域探索問題」に拡張する。

　第三に、ボロノイ図の別の利用法として、与えられた分割図形をボロノイ図で近似するという「ボロノイ図あてはめ問題」に注目する。従来の方法をまとめて、その内の「PB法」と呼ばれる方法に改良を加えると同時に、実際に自然界に見られる分割図形へこれを適用し、ボロノイ図らしい分割図形の中にはボロノイ図の定義に無関係な生成原理でできたものも含まれることを指摘する。さらにこの問題を拡張して、「断面ボロノイ図あてはめ問題」という問題を新しく提案する。これは3次元セル構造の断面から元の構造の性質を引き出そうとするもので、今までにない新しい視点のステレオロジーである。この問題の性質を論じ、数理計画問題に変換して反復解法によって解くことを試みる。

　われわれの住む世界は3次元空間という幾何的広がりをもつため,そこで生まれる工学的諸問題も必然的に幾何的構造を背景にもつものが多い.したがって,そのような問題に数理工学の立場から接近するための道具としての計算幾何学は,問題解決のための重要な基礎理論であり,いっそうの発展が望まれる.本論文は,このような背景のもとに,基本的な幾何データ構造の一つであるボロノイ図に着目し,その計算法の改良と応用の拡大をめざしたもので,「ボロノイ図の構成法と利用法に関する研究」と題し,9章より成る.

　第1章の「はじめに」で本論文の目的と構成を述べたあと,第2章「ボロノイ図」では,ボロノイ図の定義,その代表的構成算法の一つである逐次添加法,および一般化と応用例について述べ,以降の議論の出発点を与えている.

　第3章は「幾何アルゴリズムの加速のための混合演算諸方式の比較」と題し,ボロノイ図をロバストかつ高速に構成するために浮動小数点計算と多倍長整数計算を組み合わせる計算方式にいくつかの改良を施している.ここで提案されている新しい方法は,入力データとして与えられる浮動小数点数を加速のためにそのまま利用でき,誤差の見積りには伝播誤差だけでなく発生誤差も考慮するなどの特徴をもつ.また,誤差をより精密に見積ることは,不要な多倍長計算をより多く避けられるという意味で加速に貢献する反面,誤差の見積り自身にコストがかかるというトレードオフの関係をもつ.これに対して,精度の異なるいくつかの誤差見積り方式を比較し,入力点集合のタイプに応じて適切な方式を選択するための指針を与えるとともに,ほとんどの場合に,本論文で新たに提案した見積り方式が従来のものよりすぐれていることも示している.

　第4章「木構造だけを利用する最近点探索とボロノイ図を利用する最近点探索」では,ボロノイ図構成算法の中で部分問題として現れる最近点探索問題に焦点を合わせ,それに利用できる5種類の木構造の性能を実験的に調べている.特に,これらの木構造を単独で用いる方式と,構成途中のボロノイ図も併用する方式が,性質の異なるいくつかの入力に対してどのような性能の差をもたらすかを観察している.またもう一方では,計算時間を増大させる要因を列挙し,実験結果がそれらの要因によってよく説明できることを示すとともに,実験で調べたもの以外の入力点配置に対しても,各木構造の性能を予想することのできる枠組みを構成している.そして,木構造を単独で用いる方法と比べてボロノイ図を併用した方法の計算時間がおよそ半分になること,広い範囲の入力点分布に対して最適k-d木が最も性能がよいことなどの具体的知見も与えている.

　ここまでがボロノイ図の構成法に関する貢献であるのに対し,以下の章はボロノイ図の新しい利用法を開拓する試みである.

　第5章は,「寄り道施設探索法」と題し,与えられた経路に近い施設を列挙するというタイプの新しい幾何的問題を導入し,その解法を構成している.ここでは,近い施設の有無の判定,最も近い施設の探索,近い施設の列挙という3種類の問題を考え,いずれに対してもボロノイ図を利用したアルゴリズムを構成している.さらに,最後の問題に対するアルゴリズムは,一般の形の領域が指定されたときその内部に属す施設を列挙する領域探索問題の新解法ともなっていることを指摘している.

　第6章「2次元ボロノイ図あてはめ問題」では,与えられた分割図形がどれほどボロノイ図に近いかを示す新しい指標を提案している.この指標は,ボロノイ図との食い違いの面積に着目する従来の指標と異なり,2次関数の最小値の形で解析的に−したがって高速に−計算できるものである.さらに,この指標は,従来の指標と異なり,分割図形の中の微小領域に大きく左右されることがないという特徴をもつことも示している.

　第7章「自然界のボロノイ図」では,ひび割れや石鹸泡など自然界に現れる分割図形のボロノイ図らしさを,新しい指標を用いて調べるとともに,辺の総長の最小化や領域面積の均等化など別の原理が働く場面でもボロノイ図に近い分割図形が生じることをシミュレーションによって示し,ボロノイ図らしいと判定されたパターンであってもその背後にはボロノイ図と異なる生成原理が作用している場面も少なくないという警告も発している.

　第8章は「断面ボロノイ図あてはめ問題の提案−問題の性質・実用的な解法・応用の可能性」と題し,3次元分割図形の2次元断面図から3次元ボロノイ図らしさを判定するという新しい問題を定式化するとともに,その反復解法を構成している.そして,この産法が,積分幾何学の新しい手法を提供し得ることを指摘し,3次元分割構造の解析などへの応用の可能性も論じている.

　以上を要するに,本論文は,計算幾何学の基本データ構造の一つであるボロノイ図に関して,計算法の高速化を図るとともにいくつかの新しい応用分野を開拓したもので,数理工学の発展に大きく貢献するものである.よって本論文は,博士(工学)の学位請求論文として合格と認められる.