本論文では、3角形分割およびそれに近い対象のいくつかの組合せ的側面を研究する。d次元空間の点配置とそれらの点に頂点を持つ多面体の3角形分割とは、その多面体の、それらの点に頂点を持つd次元単体達による分解のことである。

　3角形分割が登場する2つの主な領域は、数学における組合せ幾何と、情報科学における計算幾何である。組合せ幾何で3角形分割と関連する分野としては、凸多面体の理論、アフィントーリック多様体のGrobner基底、Hilbert基底、一般化超幾何関数、Ehrhart多項式などがある。計算幾何の多くの分野、メッシュ生成、コンピュータグラフィックス、ソリッドモデリング、モーションプランニングなどで、3角形分割は重要な役割を果たしている。我々が扱う問題は、組合せ幾何の主な問題のいくつかである。本論文での話題は、計算幾何での応用よりは単純化した基本的な状況についての解析であるが、それらの応用を背景として生まれる問題であり、このような応用でなぜ/いつ上手く行くかに洞察を与えうるものになっている。

　研究の対象とするものは、3角形分割の周辺にある、抽象的あるいは幾何的な単体的複体、3角形分割、3角形分解である。具体的には、(1)3次元凸多面体の3角形分割、(2)(主に)平面の3角形分割、(3)2次元球面、(4)2次元の単体的複体、を扱った。これらはこの順に、かちっとしたものから抽象的なものになっている。これらの対象について、我々が扱った性質は、(1)サイズ、(2)正則性という実座標での3角形分割の凸性を表す性質、(3)geometric shellingという組合せトポロジー的なものに実座標での凸性を加味した性質、(4)shellability、extendable shellability、vertex decomposabilityの逐次的構成についての組合せトポロジー的な性質、である。これらはこの順に、基本的な性質から精密な性質になっている。各性質の持つ難しさは、次元が上がると大きくなるが、本研究では、上の4つのレベルについて、それぞれの次元の中で最も根本的なもの、よりかちっとした対象については基本的な性質を、より抽象的な対象については精密な性質を調べた。4つの結果を順番に紹介する。(全体の概要は第1章)

　最初のものは、分解のサイズに関するものである。3角形分解というのは、単体達が必ずしも単体的複体を作るようにきれいに交わっていなくてもよい分解のことである。3角形分解は、3角形分割を含むクラスを形作っている。我々は、3次元凸多面体についての、これらの2つの分解のクラスのサイズから見た違いを示した。また、これらの3角形分解のサイズについて、3角形分割と同様の上下限を示した。(第2章。Jesus A.de Loera、Francisco Santosとの共同研究)

　2つ目の結果は、非正則3角形分割についてのものである。3角形分割の極大次元の単体達をある点から見たときの手前/向こうでの順序を表すグラフを定義した。このグラフの中に、ある非対称的なサイクルを持つような3角形分割達は、非正則3角形分割の中で、部分クラスをなす。よって、我々は、非正則3角形分割の組合せ的な部分クラスを与えたことになり、これ自体おもしろいものである。また、線形計画の双対性を使って、さらに深くこれらの3角形分割の性質を調べた。(第3章)

　3つ目の結果も、組合せトポロジー的な性質についてのものである。ここでは、3次元凸多面体についての、幾何的なshelling、つまりある組合せ的に同値な凸多面体でline shellingとなっているもの、について研究した。shellingが幾何的なshellingになるための十分条件をいくつか示した。これは、凸多面体の理論およびグラフ理論の両方で、興味深いものである。(第4章。Takayuki Ishizekiとの共同研究)

　最後の結果は、組合せトポロジー的な性質についてのものである。ここでは、逐次的な構成についての性質、つまり、shellability、extendable shellability、vertex decomposabilityの違いについて2次元の単体的複体を対象として研究した。小さなサイズの、shellableでない非擬似多様体を列挙することにより、これらのクラスの違いを示す最小例、および知られていなかった関係を明らかにする例をみつけた。(第5章。Sonoko Moriyamaとの共同研究)

　本論文は3角形分割および関連する種々の組合せ問題に対して理論的研究を行ったものであり、6章から構成されている。3角形分割は組合せ幾何や計算幾何という観点から興味深い研究対象であるばかりでなく、メッシュ生成、コンピュータグラフィックス、ソリッドモデリング、モーションプランニングなどにおける重要な基盤技術であるため、応用面からも重要な研究対象である。

　第1章では論文全体が概観されており、研究対象とした問題、背景、関連研究、研究結果が簡潔に説明されている。

　第2章では、3角形分割および3角形分解の組合せ複雑度について研究されている。なお、3角形分解とは、単体達が必ずしも単体的複体を作るようにきれいに交わっていなくてもよいように、3角形分割の条件を緩和したものである。本章では3次元凸多面体を主対象として分割および分解が研究されている。つまり、3次元の凸多面体が最小、もしくは、最大で何個の4面体に分割もしくは分解されるか、という問題が研究されている。主な研究結果として以下のことが示されている。(i)最小の分解数は最小の分割数より小さくなり、最大の分解数は最大の分割数より大きくなるような凸多面体が存在すること。(ii)分解数と分割数に線形のギャップがある凸多面体の族が存在すること。これまで、3次元以上における分解数と分割数との関係に関して一般的な結果を得るのは困難であると考えられていたため、この結果は重要である。この結果を契機として、その関係の解明が急速に進展することが期待される。

　第3章では、非正則3角形分割のグラフ論的特徴づけが与えられている。なお、d次元3角形分割が、(d+1)次元凸多面体のある種の射影となる時、そのd次元3角形分割は正則であると定義される。正則3角形分割は幾何的に定義された概念であるが、本章では、非正則となるための十分条件がグラフ論的つまり組合せ論的に与えられている。この結果自体、非常に興味深いものであるが、この結果を証明するために使用された、線形計画の双対性に基づく証明技法は非常に新規であり、他の問題の解析にも適用できる可能性もあり、より興味深いものである。他の章の結果が論文提出者の解析能力の高さを主を示したものであるのに対し、本章の結果は論文提出者の独創性の高さを示すものであるといえる。

　第4章では、3次元凸多面体における、面の順序づけに関連した、shellingと呼ばれる性質について研究されている。結果として、組合せトポロジー的に定義されたshellingという性質を持つ多面体が、幾何的に定義されたgeometric shellingという性質を満たすための十分条件が与えられている。

　第5章でも、組合せトポロジー的な性質についての研究がなされている。具体的には、単体的複体の逐次的な構成に関する性質である、shellability、extendable shellability,vertex decomposabilityについて、2次元の単体的複体を対象に研究し、これらのクラスの違いを示す最小の例および新たな関係を明らかにする例を発見している。

　本論文の理論的結果を得ることを支援するために、計算機による例の生成・テストが有効に活用された。純粋な理論研究に計算機を応用することは興味深いアプローチである。第6章には、そのために用いた手法やアルゴリズムに関する事項が簡潔にまとめられている。

　本論文では、これまで数多くの研究がなされ、多くの困難な問題が残されてきた3角形分割に関する諸問題という困難な研究テーマに取り組んでいる。その結果として、新たなクラス分け、新たな特徴づけ、分割数の上下限の改善や新規導出などが行われ、3角形分割の理論的側面の理解に確実に進展をもたらした。よって、本論文に述べられた研究成果は情報科学の基礎的および理論的側面の進展に寄与するものである。 なお、本論文の第2章はJesus A.de Loera氏,Francisco Santos氏との、第4章はTakayuki Ishizeki氏との、第5章はSonoko Moriyama氏との共同研究であるが、そのすべてにおいて論文提出者は共同研究者と対等以上の貢献をしており、論文提出者の寄与が十分であると判断する。

　したがって、博士(理学)を授与できると認める。