概 要
本文はこれから研究を始めようとする学生の皆さんにいかにして論文を書くかを伝えようとするものである．もちろん，一般的な法則などあり得ないが，着眼点は何かを少しでも伝えたい．他の研究分野では事情が異なることもあるので，本文では計算幾何学に限定して話を進める．

計算幾何学でいかに論文を書くか
北陸先端科学技術大学院大学
情報科学研究科浅野哲夫  

平成年月日

まえがき
計算幾何学で論文を書くためには，まず計算幾何学の勉強から始めなければならない．いきなり論文を読むのは辛いので，計算幾何学に関する入門書から勉強を始めることになる．ある程度の知識が得られたら，国際会議の論文を読み，さらに国際ジャーナル誌の論文を精読するというのが一般的な順序であろう．入門書レベルの学習は楽しいが，論文レベルになると，なぜこんなに分かりにくく書くのだろうと著者を恨みたくなるものである．しかし，そもそも科学論文の歴史を振り返ってみれば論文が分かりにくいのも納得できる．
計算幾何学の分野で研究論文を書くためには，もちろん，この分野の研究成果のサーベイのために論文を読むことから始めないといけないが，論文を読むのが好きで堪らないという人にまだ出会ったことがない．難解な論文を読破するという難行を経て初めて研究者の第一歩を踏み出すことができる．論文を読むという辛い時間を少しでも楽しむことはできないだろうか．
筆者は科学論文を推理小説に見立てて読むことで少しなりとも楽しみを見出そうと努めている．
何を推理するかというと，著者がどのようにして研究を進めたのかを論文の記述の端々から推理するのである．立派な論文であればあるほど，論文の著者は苦労を重ねたはずである．論文のどの個所が難関であっただろうか．その難関を乗り切るために過去の研究成果がどのように役立っているか．また，自分を著者に置き換えてみて，自分なら過去の研究成果だけから論文の研究成果を導くことはできただろうかと自問してみる．そんなことを考えながら論文を読み進めば，少しは楽しめないだろうか．
本文では，なぜ論文は読みづらいのかについて私見を述べることから始める．簡潔に言うと，論文が読みづらいのは，あるいはもっと正確には論文を読んで研究を進めようとするのが難しいのは，論文というものは研究の進行と逆の順序で書かれていることが多いからである．研究の進展を日記風に綴った書き物があれば非常に参考になると思われるが，未だにお目にかかったことはない．そのことを理解してもらった上で，計算幾何学の分野で論文を書くためのヒントになりそうなものを幾つか提案したい．まず，計算幾何学の歴史を簡単に振り返った後，代表的な問題と研究成果を紹介する．



なぜ論文は読みづらいのか

インターネットも電子出版も存在しない大昔から科学論文は存在する．筆者が学生であった時代でも，学会の論文誌は活字を組んで印刷されていた．複雑な数式を正しく活字に組むには植字工の熟練技術が必要な時代であった．そのため印刷物は高価なものであり，費用を抑制するためには論文を短くすることが求められた．そこで，常識として片付けることができる程度の証明などは削って，必要最低限の情報だけを記述するという習慣が生まれた．どこまでを常識レベルとするかが問題であるが，自らの知識レベルをひけらかしたいほどレベルを上げるのが人の常である．かくして，科学技術論文は一定の知識がなければ読めないものになってしまった．著者の方にも，いちいち初学者には付き合っていられないという思いがあるのも当然のことである．
他にも論文を読んで関連研究を始めるときに障害になることがある．それは論文のスタイルそのものにも関係する．科学論文では，簡潔に研究成果を説明することが要求される．数学では「定理の美しさ」が今なお重要な要素である．同じ定理であっても，長々と記述するのではなく，簡潔に表現された定理が好まれるのである．たとえば，「すべての平面地図は  色で塗り分けられる」というグラフ理論における  色定理は余りにも有名であるが，見事なまでに簡潔に表現されている．この簡潔な表現を支えるのが定義である．計算幾何学においても数学と同様に多くの定義があるが，およそ立派な論文ほど，複雑な概念を簡潔に表現した優れた定義を含むものである．しかも，定義は論文の中では主要な定理の前に存在する．これが問題である．
確かに，定義さえ理解できれば，定理の証明も見通しが良くなり，論文全体の理解にかかる時間も大いに短縮される．
では，なぜ定義が問題なのか．論文が完成するまでの研究の経過を考えてみよう．論文の著者は最初から定義を思いついた訳ではないだろう．余程の天才でない限り，最初は成り立ってほしい定理を予想することから始め，小さな例題について定理の性質が成り立つかどうかを手で検証する．凡人は思い込みで支配されているので，なかなか自分にとって都合の悪い例題を考え付くのは難しいが，とにかく徐々に例題を複雑にしていく．不幸にも予想定理の反例が見つかった場合には予想定理を手直する．何度かの手直しの後で確信が持てれば，証明に取りかかる．このときに最も重要なことは全ての場合が尽くされているかどうかである．素朴な方法
は場合分けである．すべての場合について定理が成り立つことを証明できれば，論文はかなり完成に近づいたことになる．このままの形で論文にまとめて国際会議やジャーナルに投稿しても，まずそのまま受理されることはないだろう．内容が洗練されていないからである．正しいということだけでは価値がないのである．
ここで定義が登場する．多くの場合分けをまとめて，簡潔に表現するために新たな概念の定義が必要である．どんな定義を思いつくかで論文の価値が決まると言って過言でない．良い定義を思いつけば頭の中が整理されて，更に別の問題にも同じ定義が応用できることが分かった
りする．このように，定義は研究を進めていく上で遅い段階で生み出されることが多い．その定義が論文においてはまっ先に登場するので，研究論文を書いたことがない学生が初めて読むと，研究では先に定義が必要なのかと思ってしまうことがある．もちろん，例外は無数にある．
良い定義を思いついて研究が進むということもあるが，計算幾何学の分野では定義が後に来る方が一般的であろう．



問題の発見

筆者が属する北陸先端科学技術大学院大学は大学院だけの大学であるが，博士前期課程においては問題解決能力を，博士後期課程においては問題発見能力を養うことを目標に置いている．
問題解決能力とは，問題が与えられたときに既に開発された技法に基づいて解決する能力のことである．たとえば，平面上に与えられた多数の点を包含する最小の凸多角形（凸包）を求めるアルゴリズムを設計するのに分割統治法を用いようと決めれば，どのように点集合を部分集合に分割し，それぞれの部分集合に対して再帰的に構成された凸包をどのように統合して，元の点集合に対する凸包を計算するかを考える．分割統治法の例を多数知っていれば，これはそれほど難しいことではない．
問題発見能力とは何だろう．上の例では，与えられた点を全て含む最小の凸多角形を求めれば，それが他の問題を解くのに非常に役に立つのではないかということを発見することである．
問題解決能力は多数のテキストを読んで経験を積み重ねれば，自然と向上するものであろう．
しかし，問題発見能力では新たな発見が必要なので，問題解決能力に比べてより年季が必要になる．
計算幾何学における論文は千差万別であるが，最も評価が高いのは，多様な問題に統一的に適用可能な一般的な概念に基づいたアルゴリズム設計の基本原理を提案するものである．そのためには，まず計算幾何学でどのような問題が研究され，どんなアルゴリズム設計原理が開発されてきたかを良く学習しておく必要がある．

計算幾何学の歴史と発展

計算幾何学は，幾何的な性質をうまく利用して効率の良いアルゴリズムを開発することと，幾何的に問題の本質的な計算困難度を解析することを目的としている．計算幾何学の誕生を何年と特定するのは難しいが，  年代と考えるのが妥当なようである．したがって，まだ  年に満たない若い学問分野である．したがって，いわゆる長老と呼ばれる研究者が少なく，上下関係が希薄な気楽なコミュニティーを構成している．
計算幾何学で最初に扱われた問題は平面上の凸包構成問題である．点集合 Ë の凸包とは， Ëの点をすべて内に含む最小の凸多角形のことである．今でこそ凸包が多項式時間で構成できることは自明であるが，筆者が最初にこの問題を聞いたときにはどんな素朴な方法も考え付かなかった．幾何的な問題を考えるということに慣れていなかったからである．当然のことながら，計算幾何学で論文を書くためには計算幾何学の分野でどんな問題が解かれ，どんなアルゴリズム設計技法や証明技法が開発されてきたのかを知っておく必要がある．
手っ取り早く計算幾何学で扱われた問題と結果を知るには，ハンドブックを紐解くことであろう．現在のところ  冊のハンドブックが出版されているが，ごく最近の研究成果を除いて重要な研究成果はほぼカバーされている   ．



計算幾何学の代表的な問題と研究成果

ここでは簡単に研究幾何学における代表的な問題を紹介しながら，研究をどのように発展させるかについても述べる．最初は点位置決定問題である．これは，平面上に直線だけで描かれた地図が与えられているとき，任意に指定された点を含む領域につけられた名前を答えるといÒ 時間の前処理で平面地図をデータ構造う問題である．線分の本数を Ò とするとき， Ç Òに蓄えておくと，毎回の質問に ÇÒ 時間で答えることができる．
ここまでの記述で既にお気づきのことと思うが，計算幾何学ではアルゴリズムの漸近的な振舞いに関心がある．つまり，データサイズが  倍になったときに，実行時間は何倍になるかを知りたい．実行時間が Ç Ò  であれば，データサイズが  倍になれば実行時間は  倍になり，Ç Ò  であれば，   倍になる．その意味で，Ç Ò と Ç Ò Ò は大差がないが，理論家にとってはÒ のファクターを如何に取るかが大きな問題になる．
計算幾何学で最も有名な構造はボロノイ図であろう．これは，多数の点が与えられているとき，どの点に最も近いかで平面を領域に分割した図のことである．図 左 に簡単な例を示す．
点の勢力圏を表していると見ることもできるので，植物学を始め多数の応用がある．この図があれば，任意の点を指定したとき，それがどの点に最も近いかを求めることは自明なように思われるが，実はそれほど自明ではない．人間は目を持っているので，質問点がどの領域に含まれるかを見ることができるが，計算機では計算で求める必要がある．しかし，上に述べた点
Ò 時間でどれが最も近い点かを位置決定のデータ構造とアルゴリズムを知っていれば， Ç答えることができる．

図  点集合に対するボロノイ図（左）と対応するデローネイ三角形分割（右）ボロノイ図と並んで重要な概念が三角形分割である．これは，与えられた点だけを頂点として，点集合の凸包の内部を三角形に分割するものである．そのために与えられた  点を線分で結ぶという操作を繰り返すが，出来上がった図は三角形だけで構成されていることを保証するた
めには，どの  本の線分も交差してはならない．当然，同じ点集合に対しても何通りもの三角形分割が考えられるが，点の個数を Ò とすれば，異なる三角形分割の個数は Ò に関して指数関数的に増大することが知られている．そのように多数の三角形分割の中で，細長い三角形を含まないもの，数学的には含まれる三角形の内角の最小値を最大にするようなものが実用的には意味がある．そのような最適な三角形分割を求めるのに，三角形分割の質を逐次的に改善していく方法も考えられるが，実は，ボロノイ図の双対を取れば（最小内角を最大にするという意味で）最適な三角形分割が得られることが分かっている（図 右 参照）．ボロノイ図が Ç ÒÒ 時間で構成できるので，そのような最適な三角形分割も Ç ÒÒ 時間で計算することができる．
三角形の質を最小内角の大きさ以外で評価する場合には当然の事ながら計算複雑度も変わる．
三角形分割のために引いた線分の長さの総和を最小にする問題は最近になって 困難である
ことが証明された  ．筆者自身が興味を持っているのは，アスペクト比と呼ばれる評価基準である．これは三角形の最小の高さを最長辺の長さで割った値である．正三角形のときに比が最大になる．三角形分割に含まれる三角形のアスペクト比の中で最悪のもので三角形分割の質を定めるとき，最適な三角形分割を求める問題はボロノイ図の双対のように多項式時間で求めることができるだろうか，それとも 困難であろうか．実は，どちらか全く知られていない．
点集合ではなくて，一筆書きできる多角形の内部を三角形に分割するという問題もある．点集合の場合と同じように， Ò 頂点の多角形を Ç ÒÒ 時間で三角形分割することは比較的容易であるが，もっと高速にできるかどうかが長年の未解決問題であった．この問題はプリンストン大学のシャゼール    の線形時間のアルゴリズムによって肯定的に解かれた．いまなお，彼の論文  は計算幾何学における最高の論文と評価されている．
このように，同じ問題であっても評価の方法を変えると別の問題を定義することができる．
ただ，どんな評価方法でもよいという訳ではなく，意味があると思われるものでなければならない．

研究の方向性

計算幾何学はかなり実学に近い学問分野である．歴史の初めにおいては理論計算機科学の中でもかなり数学に近い存在であり，組み合せ数学的側面が重視される傾向にあった．平面上に多数の線分が与えられたとき，それらの接続・交差関係によって一種のグラフ構造が定義できるが，その数学的性質が研究の対象となり，多数の論文が書かれた．実際，それらの数学的性質がアルゴリズムにも利用され，効率の良いアルゴリズムの開発にもつながっている．上述のボロノイ図についても様々な数学的性質が調べられたが，一方でプログラムとしての実装についても様々な角度から研究が行われた．点集合の場合には代表的なアルゴリズム設計技法である
分割統治法で効率の良いアルゴリズムを構成することができるが， 次元の構造を利用して平面のボロノイ図を構成することも可能である．また，実際にプログラムを実行してみると，計算誤差によってプログラムが暴走してしまうことがある．これを防ぐにはどうすればよいかについても様々な方式が考えられている．
このように，一つの幾何的問題に対して効率の良いアルゴリズムを設計することはもっとも重要な研究テーマであるが，（漸近的な意味で）理論的に最適なアルゴリズムが得られても，少し設定を変えるだけで新たな問題点が現れる．計算幾何学では無理矢理に新たな設定を考えるのではなく，最終的には効率の良い信頼できるプログラムの開発を目指しているので，その方向に向けて新たな問題点を考えて研究の種にする，というのが一般的な傾向である．

むすび

本文では計算幾何学の分野で研究を進めるのに何に注意すべきかを述べようとした．最も言いたかったことは，計算幾何学は理論でありながら，最終的な目標を実装に置いているので，その方向に向けて幾らでも研究の種はあるということである．筆者の力不足のために十分に伝わったかどうか甚だ疑問であるが，これを契機に一人でも計算幾何学に興味をもってもらえれば幸せである．

参考文献．   !" # $!"  %!&'  ' ( " !" !" $!& )!%* $ "+  &'#$$! ", &$ (，-     '' .，  

 /．0．, +&" "+ /．123 # 4，+，5"+6 4 7 )!%* $ "+  &'#$$! " ,&$ (，8* "+ 0+!$! " 3  %% 99，
 : ;#  "+ , 3 $ ;!"!&#&<! $ $ !" # $! " !%  + / =; -    ''    . /3．8*4 "+ /．> #$!，+，5"+6

4 7  &'#$$! " , &$ (  $ 5"+，

著者紹介
浅野 哲夫：  年  月  日生．昭  大阪大学大学院博士課程修了．大阪電気通信大学を経て，現在，北陸先端科学技術大学院大学情報科学研究科教授．主として計算幾何学と組み合せ最適化の研究に従事．

