目次

第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 格子簡約の応用

ページの先頭へ