• ニュースメール
  • アフターサービス
  • 教科書献本のご案内
  • facebook
  • 構造計画研究所

計算幾何―理論の基礎から実装まで― 

書籍情報
シリーズ名アルゴリズム・サイエンスシリーズ 全16巻 数理技法編 【10】巻
ISBN978-4-320-12176-8
ページ数252ページ
発行年月2007年01月
本体価格3,300円
計算幾何 書影
計算幾何

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

目次

第1章 計算幾何学とは何か
1.1 計算幾何学の歴史
1.2 幾何問題のむずかしさ
1.3 計算幾何学の代表的問題
1.4 アルゴリズムの効率
章末問題

第2章 計算幾何の基礎
2.1 点の表現
2.2 直線の表現
2.3 線分の表現
2.4 符号付面積
2.5 線分の交差判定
2.6 円の内部と外部の判定
2.7 3角形に関する問題
2.8 記号摂動法
章末問題

第3章 幾何計算の実装
3.1 計算幾何とLEDA
3.2 pointデータタイプ
3.3 segmentデータタイプ
3.4 rayデータタイプ
3.5 lineデータタイプ
3.6 vectorデータタイプ
3.7 circleデータタイプ
3.8 polygonデータタイプ
章末問題

第4章 計算幾何学の基本的な考え方
4.1 多角形と多角形領域
4.2 平面地図と二重連結辺リスト
4.3 凸多角形に関する計算
4.4 凸多角形の直径の計算
4.5 凸多角形の内部と外部の判定
4.6 凸多角形への接線
4.7 凸包の計算
章末問題

第5章 基本的なアルゴリズム設計技法
5.1 再帰
5.2 分割統治法
5.3 逐次構成法
5.4 グリーディ法
5.5 動的計画法
5.6 線形計画法
5.7 パラメトリック探索
5.8 縮小法
章末問題

第6章 乱択アルゴリズム
6.1 乱数をいかに使うか
6.2 モンテカルロアルゴリズム
6.3 ラスベガスアルゴリズム
6.4 確率的丸めに基づく乱択アルゴリズム
6.5 ランダムサンプリング
章末問題

第7章 幾何計算のためのデータ構造
7.1 1次元データのためのデータ構造
7.2 セグメント木
7.3 インタバル木
7.4 領域探索のためのデータ構造
章末問題

第8章 計算幾何のためのアルゴリズム設計技法
8.1 平面走査法
8.2 幾何学的変換法
8.3 高速行列探索法
8.4 トポロジカルスィープ
8.5 トポロジカルウォーク
章末問題

第9章 ボロノイ図とデローネイ3角形分割
9.1 ボロノイ図
9.2 最近点問題と最近点対問題
9.3 デローネイ3角形分割
9.4 最遠点ボロノイ図
章末問題

第10章 メモリ階層を考慮したアルゴリズム
10.1 メモリの階層構造
10.2 入出力効率のよいアルゴリズム
10.3 入出力効率のよい平面走査法
10.4 入出力効率のよいデータ構造
章末問題

付録 数学的基礎とおもな公式
付録1 漸近記法
付録2 基本的な公式と記号の定義
付録3 漸化式の解法

章末問題へのヒント
索引