1 計算幾何学
入門　　
1.1 凸包の例
1.2 縮退と頑健性
1.3 応用分野
1.4 文献と注釈
1.5 演習

2 線分交差
テーマ別地図の重ね合せ　　　
2.1 線分の交差
2.2 2 重連結辺リスト
2.3 2 つの平面分割の重ね合せ
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 演習

5 直交領域探索
データベースの検索
5.1 1 次元領域探索
5.2 kd-木
5.3 領域木
5.4 高次元領域木
5.5 一般の点集合
5.6* フラクショナルカスケーディング
5.7 文献と注釈
5.8 演習

6 点位置決定問題
現在位置を知ること
6.1 点位置決定と台形地図
6.2 乱択逐次構成アルゴリズム
6.3 縮退の取扱い
6.4* 末尾評価
6.5 文献と注釈
6.6 演習

7 ボロノイ図
郵便局問題
7.1 定義と基本的な性質
7.2 ボロノイ図の計算
7.3 線分のボロノイ図
7.4 最遠点ボロノイ図
7.5 文献と注釈
7.6 演習

8 アレンジメントと双対性
光線追跡法におけるスーパーサンプリング　　　
8.1 ディスクレパンシの計算
8.2 双対性
8.3 直線のアレンジメント
8.4 レベルとディスクレパンシ
8.5 文献と注釈
8.6 演習

9 ドロネー三角形分割
高さ方向の補間　　　
9.1 平面上の点集合の三角形分割
9.2 ドロネー三角形分割
9.3 ドロネー三角形分割の計算
9.4 解析
9.5* 乱択アルゴリズムの枠組み
9.6 文献と注釈
9.7 演習

10 幾何データ構造
ウィンドウ処理　　　
10.1 区間木
10.2 プライオリティ探索木
10.3 区分木
10.4 文献と注釈
10.5 演習
11 凸包

物体の混合　　　
11.1 3 次元空間における凸包の複雑度
11.2 3 次元空間での凸包の計算
11.3* 解析
11.4* 凸包と半空間の交差
11.5* ボロノイ図（その 2）
11.6 文献と注釈
11.7 演習

12 空間 2 分割
塗り重ね法　　　
12.1 BSP 木の定義
12.2 BSP 木と塗り重ね法
12.3 BSP 木の構成法
12.4* 3 次元空間での BSP 木のサイズ
12.5 低密度のシーンに対する BSP 木
12.6 文献と注釈
12.7 演習

13 ロボットの移動計画
目的地への行き方　　　
13.1 作業空間とコンフィギュレーション空間
13.2 点ロボット
13.3 ミンコフスキー和
13.4 並進移動計画
13.5* 回転を許した場合の移動計画
13.6 文献と注釈
13.7 演習

14 4 分木
非一様なメッシュ生成　　　
14.1 一様なメッシュと非一様なメッシュ
14.2 点集合に対する 4 分木
14.3 4 分木からメッシュへ
14.4 文献と注釈
14.5 演習

15 可視グラフ
最短経路の発見　　　
15.1 点ロボットに対する最短経路
15.2 可視グラフを求める方法
15.3 並進多角形ロボットに対する最短経路
15.4 文献と注釈
15.5 演習

16 単体領域探索
ウィンドウ操作（その 2）　　　
16.1 分割木
16.2 マルチレベル分割木
16.3 切断木
16.4 文献と注釈
16.5 演習

参考文献
索引