出版社内容情報
【目次】
1. 序―２つの幾何学
1.1 画廊定理
1.2 離散幾何学と計算幾何学
1.3 演習問題
1.4 文献ノート
2. 直径と凸包
2.1 点集合の直径
2.2 凸包
2.3 対蹠点対
2.4 真の対蹠点対の計算
2.5 凸包の計算
2.6 凸包アルゴリズムの実現
2.7 演習問題
2.8 文献ノート
3. 最遠点対と行列の最大値問題
3.1 最遠点対の数
3.2 凸多角形に対する最遠点対アルゴリズム
3.3 単調行列の行最大値
3.4 演習問題
3.5 文献ノート
4. 交わり
4.1 Radon分割とHellyの定理
4.2 点集合のｋ-核
4.3 Radon分割の一般化
4.4 横断線
4.5 演習問題
4.6 文献ノート
5. 幾何学的列挙
5.1 直線配置
5.2 十字法
5.3 辞書とピボット
5.4 辞書の列挙
5.5 超平面配置の頂点列挙
5.6 多面体の頂点列挙
5.7 凸包の面の列挙
5.8 計算量
5.9 演習問題
5.10 文献ノート
6. 線形計画法に対する十字法の有限停止法
6.1 線形計画問題と解
6.2 十字法と終了辞書
6.3 部分問題と概終了辞書
6.4 十字法の有限停止性
6.5 文献ノート
7. 参考文献
8. 索 引
内容説明
本書は、読者の皆さんに、計算幾何学と呼ばれるコンピュータサイエンスの比較的新しい分野と、それに比べるといくらか古い数学の分野である離散幾何学とを紹介するものです。その意図は、数学の理論と、効率のよい幾何学的アルゴリズムの設計・解析との相互作用を明らかにすることです。
目次
１ 序―２つの幾何学
２ 直径と凸包
３ 最遠点対と行列の最大値問題
４ 交わり
５ 幾何学的列挙
６ 線形計画法に対する十字法の有限停止性
