計算幾何: 理論の基礎から実装まで (アルゴリズム・サイエンスシリーズ 10 数理技法編)

著者 : 浅野哲夫

• 共立出版 (2007年1月24日発売)

作品紹介・あらすじ

　計算幾何学の研究が始まって、はや30年が過ぎようとしている。今では、計算機科学の理論に関するどの国際会議の投稿案内を見ても、計算幾何学が確固とした地位を築いていることは明白であるが、残念ながら、それは計算機科学の理論研究者には当てはまっても、情報以外の研究者や情報科学の学生でさえ、計算幾何学がどんな学問であるかを正確に理解している者は多いとはいえないのが現状であろう。計算幾何学というタイトルの本が、理系の本をそろえた大型書店ですら「計算機科学」ではなく「数学」のコーナーに配架されていることが多いのは、その証拠のひとつということができる。
　「計算幾何学」という日本語名は、'computational geometry'という英語名の翻訳であるが、この名前が誤解を生んでいるように思えてならない。そこで、本書のタイトルは「計算幾何学」ではなく、計算の重みをもっと増やした表現である「計算幾何」とした。
　アルゴリズムは難解だという巷の評価があるが、計算幾何学はアルゴリズムの中でももっとも実学に近い存在ではないだろうか。もちろん、組合せ幾何学に代表される数学的な側面も計算幾何学の重要な一面であるが、実装の面で生じるさまざまな問題に真摯に耳を傾けてきている。実装の際に生じる縮退をどのように扱うか、計算誤差による暴走をどのように防ぐか、主メモリだけではなく外部メモリへのアクセスも考慮したアルゴリズムをどう設計するかなど、いずれも実装から生じた問題点の解決策である。
このような観点から、本書では通り一遍の理論だけではなく、理論の成果を実装上でどのように活用するかに焦点を当てた。もちろん、実際のプログラムでは数値誤差に対する対策や、予想しない入力に対処する方法などが必要であるが、紙数の関係上それらの問題については言及できなかった。実装を重視する立場から、もっと多くのプログラムを掲載したかったが、紙数の制限で断念せざるをえなかった。本文に盛り込むことは紙数の関係でむずかしくても、最近ではインターネットで公開するという手もあるので、なんらかの形でせっかく作成したプログラムも公開できればと考えている。
　本書は「アルゴリズム・サイエンス シリーズ」と題するシリーズ本のうちの1冊である。計算幾何学の分野で国内では長く研究に従事しているために著者が担当することになったのであるが、なぜ本書の執筆を引き受けたかというと、いちど自分の不確かな知識を整理したいと思っていたからである．また、むずかしいからという理由で避けていた理論にも挑戦してみたかったからである。パラメトリック探索の技法は計算幾何学で重要であるが、今まで自分のものになっていなかったので、これをよい機会としたかった。
（「まえがき」より）

感想・レビュー・書評

[tetsu5902さんの感想 · 2011年4月24日]

証明が説明不足な所が結構あった．

著者プロフィール

浅野 哲夫：北陸先端科学技術大学院大学教授

「2013年 『アルゴリズムイントロダクション 第3版　総合版』 で使われていた紹介文から引用しています。」