計算折り紙入門を読んでるので、それについてメモ。

教科書的な本である。

目次

1. 展開図入門
2. 展開図のアルゴリズム
3. 折りのアルゴリズムと計算量
4. 発展問題

展開図入門

展開図と辺展開図

展開図の基礎知識

1. 展開図の基本的な性質
2. 辺展開図の個数
3. 秋山・奈良の定理
   1. 回転ベルトによる無限種類の折り
   2. 秋山・奈良の定理の拡張

展開図のアルゴリズム

複数の直方体が折れる展開図

1. いくつかの準備
2. ２つの直方体が折れる展開図
   1. 全域木をランダムに生成する方法
   2. 共通の展開図を直接探すアルゴリズム
   3. 力技で全探索するアルゴリズム
3. 数々の興味深い展開図
   1. タイリング展開図
   2. 折り線が交差しない展開図
   3. 折り線が独立な展開図
   4. 無限種類の展開図
   5. 発展問題
4. 3つの直方体が折れる展開図
   1. 特殊な面積30の探索
   2. まったく新たなアイデアに基づく方法
5. 本章のまとめと未解決問題
   1. 回転対称展開図
6. おまけ問題

多面体の共通な展開図

1. 正多面体の分類
   1. 整凸面多面体
2. 正多面体の共通の辺展開の不可能性
3. 正四面体と立方体との共通の展開図
   1. 共通の展開図の生成手順
   2. 本節のまとめと課題
   3. おまけ

折りのアルゴリズムと計算量

折りのアルゴリズムと計算量とはなにか

1. 1次元等間隔折り紙モデル
   1. 基本的な定理
2. 単純折りモデルと等間隔モデルにおける万能性
3. 切手折り問題
   1. 上界の証明
   2. 下界の照明
4. 切手折り問題の折り計算量
   1. 折り計算量の基本的な性質
   2. 蛇腹折りに対するアルゴリズム
   3. 一般のパターンに対するアルゴリズムと下界
5. 切手折り問題の折り目幅問題
   1. 最適化問題と計算量
   2. 最大値の最小化問題のNP完全性
   3. 固定パラメータ容易性

発展問題

ペタル型の仮で折れるピラミッド型

ジッパー展開

レプ・キューブ

正四面体とジョンソン＝ザルガラー立体との共通の展開図

折りの判定不可能性

演習問題の解答