まえがき
計算幾何学の研究が始まって，はや30年が過ぎようとしている．今では，計 算機科学の理論に関するどの国際会議の投稿案内を見ても，計算幾何学が確固 とした地位を築いていることは明白であるが，残念ながら，それは計算機科学 の理論研究者には当てはまっても，情報以外の研究者や情報科学の学生でさえ， 計算幾何学がどんな学問であるかを正確に理解している者は多いとはいえない のが現状であろう．計算幾何学というタイトルの本が，理系の本をそろえた大 型書店ですら「計算機科学」ではなく「数学」のコーナーに配架されているこ とが多いのは，その証拠のひとつということができる． 「計算幾何学」という日本語名は，‘computational geometry’という英語名 の翻訳であるが，この名前が誤解を生んでいるように思えてならない．そこで， 本書のタイトルは「計算幾何学」ではなく，計算の重みをもっと増やした表現 である「計算幾何」とした． アルゴリズムは難解だという巷の評価があるが，計算幾何学はアルゴリズム の中でももっとも実学に近い存在ではないだろうか．もちろん，組合せ幾何学 に代表される数学的な側面も計算幾何学の重要な一面であるが，実装の面で生 じるさまざまな問題に真摯に耳を傾けてきている．実装の際に生じる縮退をど のように扱うか，計算誤差による暴走をどのように防ぐか，主メモリだけでは なく外部メモリへのアクセスも考慮したアルゴリズムをどう設計するかなど， いずれも実装から生じた問題点の解決策である． このような観点から，本書では通り一遍の理論だけではなく，理論の成果を 実装上でどのように活用するかに焦点を当てた．もちろん，実際のプログラム では数値誤差に対する対策や，予想しない入力に対処する方法などが必要であ るが，紙数の関係上それらの問題については言及できなかった．実装を重視す る立場から，もっと多くのプログラムを掲載したかったが，紙数の制限で断念vi ——まえがき せざるをえなかった．本文に盛り込むことは紙数の関係でむずかしくても，最 近ではインターネットで公開するという手もあるので，なんらかの形でせっか く作成したプログラムも公開できればと考えている． 本書は「アルゴリズム・サイエンス シリーズ」と題するシリーズ本のうちの １冊である．計算幾何学の分野で国内では長く研究に従事しているために著者 が担当することになったのであるが，なぜ本書の執筆を引き受けたかというと， いちど自分の不確かな知識を整理したいと思っていたからである．また，むず かしいからという理由で避けていた理論にも挑戦してみたかったからである． パラメトリック探索の技法は計算幾何学で重要であるが，今まで自分のものに なっていなかったので，これをよい機会としたかった． 最後に，本書の刊行にあたって多数の友人から励ましと援助をいただいた． とくに，シリーズ編集委員の杉原厚吉先生と渡辺治先生からは詳細なコメント をいただいた．長年の友人である徳山豪氏，加藤直樹氏，玉木久夫氏には有形 無形の援助を受けた．また，岩間一雄氏からの強い励ましも心強かった．同じ 講座の上原隆平氏と元木光雄氏を始めとする研究室のメンバーには，ゼミなど を通じてさまざまなバグを発見してもらった．講演の内容を第10章「メモリ 階層を考慮したアルゴリズム」に転載することを快諾してくれたLars Arge氏 にも感謝したい．共立出版編集部の小山透氏，浦山毅氏にも細部にまで目を通 していただき，拙著の中でも最もミスの少ない本に仕上がったのではないかと 信じている．以上，心からお礼を申し上げる次第である． 2006年11月 北陸先端科学技術大学院大学 浅野哲夫
