計算幾何：算法設計與分析（第3版），是中國計算機學會學術著作叢書系列，作者為周培德，於2008年7月出版。
本書可作為高等院校計算機專業研究生或本科高年級學生的教材，也可作為相關專業科技工作者的參考書。
基本介紹
圖書簡介,目錄,第0章預備知識,第1章幾何查找(檢索),第2章多邊形,第3章凸殼及其套用,第4章Voronoi圖、三角剖分及其套用,第5章交與並及其套用,第6章多邊形的獲取及相關問題,第7章幾何體的劃分與等分,第8章算法的運動規劃,第9章幾何拓撲網路設計,第10章隨機幾何算法與並行幾何算法,待解決的問題,算法一覽,參考文獻,名詞索引,
圖書簡介
本書系統地介紹了計算幾何中的基本概念、求解諸多問題的算法及複雜性分析，概括了求解幾何問題所特有的許多思想方法、幾何結構與數據結構。全書共分11章，包括: 預備知識，幾何查找（檢索），多邊形，凸殼及其套用，Voronoi圖、三角剖分及其套用，交與並及其套用，多邊形的獲取及相關問題，幾何體的劃分與等分、算法的運動規劃、幾何拓撲網路設計、隨機幾何算法與並行幾何算法等。
第3版前言
第3版對第2版的補充與修改如下： 新增26節(1.5,1.6,3.7,4.6,4.7,4.8.10,4.8.11,6.3~6.6,6.13~6.16,7.1~7.6,8.8~8.10,9.3.3,9.4.3)，刪去2章（2版中的第6章與第7章），修改4節（2.4,3.1,4.8.6,4.8.9）。新增的內容全部是作者於2005年5月至2007年12月的研究成果（其中包括71個算法，使作者設計的Z算法增至157個，占全書算法總數77%）。此外，還增加了作者提出的3個待解決問題及名詞索引。
需要說明的兩點是：
（1） 刪去第2版中的第6章與第7章，並非因為內容過時，而僅僅是為了壓縮篇幅。需要這兩章內容的讀者請參見本書第2版或者其他文獻。
（2） 對於處特殊位置的幾何體（比如多點共線），只要先加以判定，然後再處理。一般說來，比較容易解決。故本書多數Z算法的描述中，均假設幾何體處一般位置。此外，對於某些類似情況及實現某些步驟的計算技巧亦省略敘述。故讀者使用這些Z算法時要仔細研究並作必要補充。
鑒於作者水平有限，書中必有缺點和錯誤，敬請讀者批評指正。
目錄
第0章預備知識
0.1算法與數據結構
0.1.1算法
0.1.2數據結構
0.2相關的幾何知識
0.2.1基本定義
0.2.2線性變換群下的不變數
0.2.3幾何對偶性
0.3計算模型
第1章幾何查找(檢索)
1.1點定位問題
1.1.1點q是否在多邊形P內
1.1.2確定點q在平面剖分中的位置
1.1.3Z1-3算法(判定點q在哪個三角形的算法)
1.2範圍查找問題
1.2.1多維二叉樹(k-D樹)的方法
1.2.2直接存取方法
1.2.3範圍樹方法
1.3判定點集是否在多邊形內
1.4平面網路的處理與點q的定位
1.5平面上鏈的處理與點q的定位
1.6平面上線段的處理與點q的定位
第2章多邊形
2.1凸多邊形
2.2簡單多邊形
2.3多邊形的三角剖分
2.4多邊形的凸劃分
第3章凸殼及其套用
3.1凸殼的基本概念
3.2計算平麵點集凸殼的算法
3.2.1卷包裹法
3.2.2格雷厄姆方法
3.2.3分治算法
3.2.4Z3-1算法與Z3-2算法（求平麵點集的凸殼）
3.2.5實時凸殼算法
3.2.6增量算法
3.2.7近似凸殼算法
3.3計算平面多邊形頂點凸殼的算法
3.4計算平面多邊形鏈頂點凸殼的算法
3.4.1概念、算法思想與描述
3.4.2解釋與時間複雜性
3.5計算平面線段集凸殼的算法
3.6計算三維空間點集凸殼的算法
3.6.1基本概念
3.6.2卷包裹法
3.6.3分治算法
3.6.4Z3-8算法（三維凸殼）
3.6.5增量算法
3.7時間複雜性低於下界O（nlogn）的凸殼算法
3.8凸殼的套用
3.8.1確定任意多邊形的凸、凹頂點
3.8.2利用凸殼求解貨郎擔問題
3.8.3凸多邊形直徑
3.8.4連線兩個多邊形成一條迴路
第4章Voronoi圖、三角剖分及其套用
4.1Voronoi圖的基本概念
4.2構造Voronoi圖的算法
4.2.1半平面的交
4.2.2增量構造方法
4.2.3分治法
4.2.4減量算法
4.2.5平面掃描算法
4.2.6構造最遠點意義下Voronoi圖的算法
4.3平麵點集的三角剖分
4.3.1平麵點集三角剖分的貪心算法
4.3.2Delaunay三角剖分與多邊形內部點集的三角剖分
4.3.3平麵點集三角剖分的算法
4.4平面線段集的三角剖分
4.5平麵點線集的三角剖分
4.6平麵點集的偽三角剖分
4.7三角剖分的表示
4.8套用
4.8.1最近鄰近
4.8.2最大化最小角的三角剖分
4.8.3最大空圓
4.8.4最小生成樹
4.8.5貨郎擔問題
4.8.6中軸
4.8.7Voronoi圖與凸殼的關係
4.8.8Voronoi圖的推廣
4.8.9有約束的Voronoi圖
4.8.10線段集的Voronoi圖
4.8.11關聯於多邊形的Voronoi圖
4.8.12幾何數據壓縮
4.8.13車輛定位導航系統的新定位算法
4.8.14調色
4.8.15點集增（刪）點之後的三角剖分
第5章交與並及其套用
5.1線段交的算法
5.2多邊形的交
5.2.1凸多邊形交的算法
5.2.2星形多邊形交的算法
5.2.3任意簡單多邊形交的算法
5.3半平面的交及其套用
5.3.1半平面的交
5.3.2兩個變數的線性規劃
5.4多邊形的並
5.5凸多面體的交
5.6套用
5.6.1地圖匹配
5.6.2地圖數據的處理
5.6.3線段與凸多面體面的交
第6章多邊形的獲取及相關問題
6.1連線不相交線段成簡單多邊形(鏈)
6.2紅外圖像邊緣提取
6.3提取可見光圖像的邊緣
6.4圖像邊界點行排列轉換為順序排列
6.5數字圖像中目標邊界的多邊形表示
6.6包含密集點、線集多邊形的獲取
6.7滿足特定條件的多邊形劃分
6.8多邊形與多邊形鏈
6.9圓弧、直線段組成的多邊形頂點凸、凹性的確定
6.10多邊形放大、縮小及移動
6.11帶狀多邊形的處理
6.12下料問題(1)
6.13下料問題（2）
6.14下料問題（3）
6.15線鋸問題
6.16多邊形（鏈）的匹配
第7章幾何體的劃分與等分
7.1平面上不同類型點集的劃分
7.2多邊形內不同類型點集的等分
7.3平面上不同類型線段集的劃分
7.4平面上不同類型線段集的等分
7.5平面上不同類型點線集的劃分與等分
7.6鏈、多邊形的劃分與等分
第8章算法的運動規劃
8.1最短路徑
8.1.1可視圖及其構造
8.1.2Z8-1算法（尋求網路中任意兩點間最短路徑的算法）
8.1.3多面體面上任意兩點之間的最短路徑
8.1.4貨運汽車調度及行駛路徑問題
8.2移動圓盤
8.3平移凸多邊形
8.4移動桿狀機器人
8.4.1格線分解
8.4.2收縮方法
8.5機器人臂的運動
8.5.1可達性
8.5.2構造可達性
8.6可分離性
8.6.1多種可分離性
8.6.2藉助於平移的可分離性
8.6.3分離問題是NP-難的
8.6.4模擬河內塔問題
8.7滿足一定條件的運動規劃
8.8多邊形內點之間的可視圖
8.9多邊形內任意兩點之間的最短路徑
8.10自主車自動定位及確定行車方向
第9章幾何拓撲網路設計
9.1G（S）問題
9.1.1最大間隙問題（MAXG）
9.1.2最小覆蓋問題（MINC）
9.1.32中心問題
9.1.4k中心問題
9.1.5最近對問題（CPP）
9.1.6所有最近鄰近問題（ANNP）
9.1.7郵局問題（POFP）
9.2G（E）問題
9.2.1EMST問題
9.2.2歐幾里得TSP
9.2.3歐幾里得最大生成樹問題（EMXT）
9.3G（S，E）問題
9.3.1歐幾里得Steiner最小樹問題（ESMT）
9.3.2直線Steiner最小樹問題（RSMT）
9.3.3求解ESMT問題的算法
9.4G（Ω）問題
9.4.1有障礙物的最大空隙問題（MAXG（Ω））
9.4.2具有障礙物的歐幾里得最短路徑問題（ESPO）
9.4.3求解E3中ESPO問題的算法
9.4.4具有障礙物的Steiner最小樹問題（ESMTO）
第10章隨機幾何算法與並行幾何算法
10.1分類和搜尋線性表的隨機算法
10.1.1隨機二叉樹
10.1.2跳越表
10.2增量算法
10.2.1四邊形分解
10.2.2凸多胞形
10.2.3Voronoi圖
10.2.4構形空間
10.3動態算法
10.4隨機抽樣
10.4.1具有限界的構形空間
10.4.2頂-向下的抽樣
10.4.3底-向上的抽樣
10.4.4動態抽樣
10.5並行幾何算法
10.5.1凸殼問題
10.5.2排列與分解
10.5.3鄰近
10.5.4幾何搜尋
10.5.5可視性和最最佳化
