計算幾何及應用

前言
第一章 引論
　1.1 幾何基礎知識
　1.1.1 基本概念
　1.1.2 幾何對偶
　1.2 算法的復雜度
　1.2.1 算法復雜度的度量方法
　1.2.2 排序時間復雜度的下界
　1.3 數據結構
　習題
　參考文獻　
第二章 二維凸包
　2.1 凸包的定義
　2.2 極端點和極端邊
　2.3 禮品包裹算法
　2.4 凸包的快速算法
　2.5 Graham算法
　2.5.1 基于堆棧的初步算法
　2.5.2 算法實現細節的討論
　2.5.3 改進的Graham算法
　2.6 下限
　2.7 增量算法
　2.8 分而治之算法
　2.8.1 算法描述
　2.8.2 算法分析
　習題
　參考文獻　
第三章 凸包擴展
　3.1 多面體
　3.1.1 引言
　3.1.2 正則多面體
　3.1.3 多面體的歐拉公式
　3.2 三維凸包算法
　3.2.1 禮品包裹算法
　3.2.2 分而治之算法
　3.2.3 增量算法
　3.3 簡單多邊形的凸包計算
　3.3.1 計算簡單多邊形凸包的局部凸算法
　3.3.2 簡單多邊形凸包計算的“陷阱”算法
　3.3.3 簡單多邊形凸包的Melkman算法
　3.4 凸包的近似算法
　3.4.1 凸包的近似算法
　3.4.2 二維凸包近似算法精度的討論及其在三維擴展
　3.4.3 近似凸包算法的應用
　3.5 點集的Maxima
　3.6 a-shapes
　3.7 點集的相關幾何圖結構
　習題
　參考文獻　
第四章 Voronoi圖
　4.1 基本概念
　4.2 半平面
　4.3 Voronoi圖的基本性質
　4.4 Voronoi圖的構造方法
　4.4.1 增量法
　4.4.2 分而治之法
　4.4.3 掃描線法
　習題
　參考文獻　
第五章 廣義Voronoi圖
　5.1 加權Voronoi圖
　5.1.1 能量圖
　5.1.2 加法加權Voronoi圖
　5.1.3 乘法加權Voronoi圖
　5.1.4 圓與球的Voronoi圖
　5.2 高階Voronoi圖
　5.2.1 基本概念
　5.2.2 基本性質
　5.3 最遠點Voronoi圖
　5.3.1 基本概念
　5.3.2 基本性質
第六章 點集的Delaunay三角剖分
第七章 多邊形剖分
第八章 幾何搜索
第九章 相交計算
第十一章 可見多邊形與可見圖
第十二章 機器人運動規劃
第十三章 隨機算法第十章 排列
第十四章 並行計算幾何
第十五章 計算幾何研究和應用舉例