単行本(実用)

<<数学>> 凸多面体と計算 / 福田公明 / 森山園子

数学
【内容紹介】
多面体計算は、1980年代後半から始まった比較的新しい研究分野であるが、一般次元の凸多面集合に関連する様々な問題を対象としている。

本書は、凸多面体の古典的な結果に加え、計算量理論とアルゴリズム設計の両方の観点から、多面体計算における基本的かつ発展的な手法を解説する書籍である。
多面体の双対性、Eulerの関係、シェラビリティー、McMullenの上限定理、Minkowski-Weylの定理、超平面アレンジメントの面数公式など、順々に解説していく。

多面体計算の研究においては、医学、工学を始めとする様々な分野に現れる多面体的構造の解析が本質的な問題解決をもたらしてきたこともあり、多面体計算の有用性は様々に確かめられてきた。
そのような意味で未知の可能性を秘めていると言える多面体計算を学ぶのに好適な書と言えるだろう。

【目次】
第1章　整数、線形方程式、計算量

1.1　有理数のサイズ

1.2　線形方程式とGaussの消去法

1.3　最大公約数の計算

1.4　双対格子

1.5　演習問題

第2章　線形不等式、凸性、多面集合

2.1　線形不等式系

2.2　LP双対性

2.3　凸性に関する3つの定理

2.4　多面集合の表現

2.5　多面集合の構造

2.6　基本的な多面集合

2.7　具体例：順序多面体

2.8　演習問題

第3章　整数包と計算量

3.1　Hilbert基底

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　演習問題

第5章　線シェリングとEulerの関係

5.1　線シェリング

5.2　セル複体と見える半球

5.3　多くの線シェリング

5.4　演習問題

第6章　McMullenの上限定理

6.1　巡回多面体と上限定理

6.2　単純多面体とh-ベクトル

6.3　具体例：巡回多面体

6.4　演習問題

第7章　多面体に関する基本計算

7.1　単純なH-冗長性検査

7.2　H-冗長性除去

7.3　H-次元の計算

7.4　非斉次から斉次への還元

7.5　具体例：マッチング多面体

7.6　演習問題

第8章　多面体表現の変換

8.1　インクリメンタルアルゴリズム

8.2　ピボットアルゴリズム

8.3　ピボットアルゴリズム対インクリメンタルアルゴリズム

8.4　具体例：双行列ゲーム

8.5　演習問題

第9章　超平面アレンジメントと点配置

9.1　ケーキカット

9.2　超平面アレンジメントとゾノトープ

9.3　超平面アレンジメントとゾノトープの面数え上げ

9.4　点配置と関連する超平面アレンジメント

9.5　演習問題

第10章　多面体のMinkowski和

10.1　線分のMinkowski和：ゾノトープ構成

10.2　一般多面体のMinkowski和

第11章　多面体計算における問題還元

11.1　多面体計算における難しい決定問題

11.2　多面体計算における難しい列挙問題

第12章　ディオファントス近似と格子簡約

12.1　ディオファントス近似

12.2　格子簡約

12.3　格子簡約の応用

付録　多面体計算の変遷