出版社内容情報
幅広い分野での応用が期待できる計算幾何学の基礎を，方法論に重点をおいて解説。〔内容〕１次元の問題と基本的なデータ構造／凸多角形に関する問題／計算幾何学の基本的な技法／凸包問題／多角形領域の基本図形への分解／可視性問題
【目次】
1. 幾何問題の難しさ
1.1 人間の視覚と計算機
1.2 計算幾何学とは
1.3 計算幾何学における理論の展開
2. １次元の問題と基本的なデータ構造
2.1 １次元探索問題
2.2 基本的なデータ構造
2.3 １次元動的探索問題
2.4 区間データの取り扱い
2.5 ソーティング法
2.6 ｋ番目の元の選択
3. 凸多角形に関する問題
3.1 凸多角形の定義と認識方法
3.2 凸多角形の直径の計算
3.3 凸多角形の内部と外部の判定
3.4 凸多角形への接線
3.5 凸多角形の交差判定
4. 計算幾何学の基本的な技法
4.1 分割統治法
4.2 逐次構成法
4.3 動的計画法
4.4 平面走査法
4.5 直線のアレンジメント
4.6 幾何学的変換法
4.7 トポロジカル・スィープ
4.8 枝刈探索法
4.9 スケーリング法
4.10 行列探索法
4.11 静的データ構造の動的化
5. 凸包問題
5.1 Grahamの方法
5.2 分割統治法に基づく方法
5.3 逐次構成法に基づく方法
5.4 幾何学的変換に基づく方法
5.5 改良型分割統治法に基づく方法
6. 多角形領域の基本図形への分解
6.1 基本図形への分割
6.2 台形への分割
6.3 三角形への分割
6.4 最小個数の基本図形への分割
6.5 近似解法の性能評価
7. 可視性問題
7.1 単純な多角形内部での可視性
7.2 平面走査法による方法
7.3 一般の場合の高速化
7.4 質問点からの可視領域を求める方法
7.5 可視グラフの構成とその応用
8. 参考文献
9. 索 引
目次
第１章 幾何問題の難しさ
第２章 １次元の問題と基本的なデータ構造
第３章 凸多角形に関する問題
第４章 計算幾何学の基本的な技法
第５章 凸包問題
第６章 多角形領域の基本図形への分解
第７章 可視性問題
-
- 和書
- ミラクルファイブ入門
