計(jì)算幾何：算法分析與設(shè)計(jì)

前言                  
                   
 第0章 預(yù)備知識(shí)                  
 0.l 算法與數(shù)據(jù)結(jié)構(gòu)                  
 0.l.l 算法                  
 0.1.2 數(shù)據(jù)結(jié)構(gòu)                  
 0.2 相關(guān)的幾何知識(shí)                  
 0.2.1 基本定義                  
 0.2.2 線性變換群下的不變量                  
 0.2.3 幾何對(duì)偶性                  
 0.3 計(jì)算模型                  
                   
 第1章 幾何查找（檢索）                  
 1.l 點(diǎn)定位問題                  
 1.l.l 點(diǎn)q是否在多邊形P內(nèi)                  
 1.l.2 確定點(diǎn)q在平面剖分中的位置                  
 l.2 范圍查找問題                  
 1.2.1 多維二叉樹（k－D樹）的方法                  
 l.22 直接存取方法                  
 1.2.3 范圍樹方法                  
 1.3 判定點(diǎn)集是否在多邊形內(nèi)                  
 1.4 平面中線段集和空間中三角形集的正交詢問                  
 l.4.l 吊床詢問及推廣的吊床詢問                  
 l.4.2 正交限制                  
                   
 第2章 多邊形                  
 2.1 凸多邊形                  
 2.2 簡單多邊形                  
 2.3 多邊形的三角剖分                  
 2.4 多邊形的凸劃分                  
                   
 第3章 凸殼                  
 3.1 凸殼的基本概念                  
 3.2 計(jì)算凸殼的算法（二維）                  
 3.2.1 卷包裹法                  
 3.2.2 格雷厄姆方法                  
 3.2.3 分治算法                  
 3.2.4 Z3-1算法和Z3-2算法                  
 3.2.5 實(shí)時(shí)凸殼算法                  
 3.2.6 增量算法                  
 3.2.7 近似凸殼算法                  
 3.3 計(jì)算凸殼的算法（三維）                  
 3.3.l 基本概念                  
 3.3.2 卷包裹法                  
 3.3.3 分治算法                  
 3.3.4 Z3-3算法                  
 3.3.5 增量算法                  
 3.4 凸殼的應(yīng)用                  
 3.4.l 確定任意多邊形的凸. 凹頂點(diǎn)                  
 3.4.2 利用凸殼求解貨郎擔(dān)問題                  
 3.4.3 凸多邊形直徑                  
 3.4.4 連接兩個(gè)多邊形成一條回路                  
                   
 第4章 Voronoi圖及其應(yīng)用                  
 4.1 Voronoi圖的基本概念                  
 4.2 構(gòu)造Voronoi圖的算法                  
 4.2.l 半平面的交                  
 4.2.2 增量構(gòu)造方法                  
 4.2.3 分治法                  
 4.2.4 減量算法                  
 4.2.5 平面掃描算法                  
 4.2.6 構(gòu)造最遠(yuǎn)點(diǎn)意義下Voronoi圖的算法                  
 4.3 平面點(diǎn)集的三角剖分                  
 4.3.l 平面點(diǎn)集三角刻分的貪心算法                  
 4.3.2 Delaunay三角剖分與多邊形內(nèi)部點(diǎn)集的三角剖分                  
 4.3.3 平面點(diǎn)集三角剖分的算法                  
 4.4 Voronoi圖與三角剖分的應(yīng)用                  
 4.4.l 最近鄰近                  
 4.4.2 最大化最小角的三角剖分                  
 4.4.3 最大空?qǐng)A                  
 4.4.4 最小生成樹                  
 4.4.5 貨郎擔(dān)問題                  
 4.4.6 中軸                  
 4.4.7 Voronoi圖與凸殼的關(guān)系                  
 4.4.8 Voronoi圖的推廣                  
 4.4.9 幾何數(shù)據(jù)壓縮                  
                   
 第5章 交與并                  
 5.1線段交的算法                  
 5.2 多邊形的交                  
 5.2.1 凸多邊形交的算法                  
 5.2.2 星形多邊形交的算法                  
 5.2.3 任意簡單多邊形交的算法                  
 5.3 半平面的交及其應(yīng)用                  
 5.3.1 半平面的交                  
 5.3.2 兩個(gè)變量的線性規(guī)劃                  
 5.4 多邊形的并                  
 5.5 凸多面體的交                  
                   
 第6章 矩形幾何                  
 6.l 判定垂直. 水平線段是否相交的算法                  
 6.2 矩形幾何問題的特征及解決問題的途徑                  
 6.3 矩形并的面積與周長                  
 6.4 矩形并的輪廓                  
 6.5 矩形并的閉包                  
 6.6 矩形并的非平凡輪廓和外輪廓                  
 6.7 矩形的交                  
 6.8 應(yīng)用舉例                  
                   
 第7章 幾何體的排列                  
 7.1 基本概念                  
 7.2 確定直線排列的算法                  
 7.3 對(duì)偶性                  
 7.4 Voronol圖                  
 7.4.1 一維情況                  
 7.4.2 二維情況                  
 7.5 應(yīng)用                  
 7.5.1 K-最近鄰近                  
 7.5.2 刪去隱藏面                  
 7.5.3 特征圖                  
 7.5.4 點(diǎn)集的分割                  
                   
 第8章 算法的運(yùn)動(dòng)規(guī)劃                  
 8.l 最短路徑                  
 8.1.l 可視圖及其構(gòu)造                  
 8.1.2 Dijkstra算法                  
 8.2 移動(dòng)圓盤                  
 8.3 平移凸多邊形                  
 8.4 移動(dòng)桿狀機(jī)器人                  
 8.4.1 網(wǎng)格分解                  
 8.4.2 收縮方法                  
 8.5 機(jī)器人臂運(yùn)動(dòng)                  
 8.5.l 可達(dá)性                  
 8.5.2 構(gòu)造可達(dá)性                  
 8.6 可分高性                  
 8.6.l 多種可分離住                  
 8.6.2 借助于平移的可分高性                  
 8.6.3 分離問題是NP一難的                  
 8.6.4 模擬河內(nèi)塔問題                  
                   
 第9章 幾何拓?fù)渚W(wǎng)絡(luò)設(shè)計(jì)                  
 9.1 G（S）問題                  
 9.1.l 最大間隙問題（MAX G）                  
 9.1.2 最小覆蓋問題（MIN C）                  
 9.1.3 最近對(duì)問題（CPP）                  
 9.l.4 所有最近鄰近問題（ANNP）                  
 9.l.5 郵局問題（POFP）                  
 9.2 G（E）問題                  
 9.2.1 EMST問題                  
 9.2.2 歐幾里德TSP                  
 9.2.3 歐幾里德最大生成樹問題（EMXT）                  
 9.3 G（S, E）問題                  
 9.3.1 歐幾里德Steiner最小樹問題（ESMT）                  
 9.3.2 直線 Steiner最小樹問題（RSMT）                  
 9.4 G（m問題                  
 9.4.l 有障礙物的最大空隙問題（MAX G（Q））                  
 9 4.2 具有障礙物的歐幾里德最短路徑問題（ESPO）                  
 9.4 3 具有障礙物的 Steiner最小樹問題（ESMTO）                  
                   
 第10章 隨機(jī)幾何算法與并行幾何算法                  
 10.l 分類和搜索線性表的隨機(jī)算法                  
 10.l.1 隨機(jī)二叉樹                  
 10.1.2 跳越表                  
 10.2 增量算法                  
 12.2.1 四邊形分解                  
 10.2.2 凸多胞形                  
 1.2.3 Voronoi圖                  
 10.2.4 構(gòu)形空間                  
 10.3 動(dòng)態(tài)算法                  
 10.4 隨機(jī)抽樣                  
 10.4.1 具有限界的構(gòu)形空間                  
 10.4.2 頂一向下的抽樣                  
 10.4.3 底一向上的抽樣                  
 10.4.4 動(dòng)態(tài)抽樣                  
 10.5 并行幾何算法                  
 10.5.l 凸殼問題                  
 10.5.2 排列與分解                  
 10.5.3 鄰近                  
 10.5.4 幾何搜索                  
 10.5.5 可視性和最優(yōu)化                  
 算法索引