計(jì)算幾何：算法設(shè)計(jì)、分析及應(yīng)用（第5版）

第0章預(yù)備知識
0.1算法與數(shù)據(jù)結(jié)構(gòu)
0.1.1算法
0.1.2數(shù)據(jù)結(jié)構(gòu)
0.2相關(guān)的幾何知識
0.2.1基本定義
0.2.2線性變換群下的不變量
0.2.3幾何對偶性
0.3計(jì)算模型
第1章幾何查找(檢索)
1.1點(diǎn)定位問題
1.1.1點(diǎn)q是否在多邊形P內(nèi)
1.1.2確定點(diǎn)q在平面剖分中的位置
1.1.3Z13算法(判定點(diǎn)q在哪個三角形的
算法)
1.2判定點(diǎn)集是否在多邊形內(nèi)
1.3平面網(wǎng)絡(luò)的處理與點(diǎn)q的定位
1.4平面上鏈的處理與點(diǎn)q的定位
1.5平面上線段的處理與點(diǎn)q的定位
1.6判定點(diǎn)是否在多邊形內(nèi)部的新算法
第2章多邊形
2.1凸多邊形
2.2簡單多邊形
2.3多邊形的三角剖分
2.4多邊形的凸劃分
2.5對多邊形鏈的監(jiān)視
2.6線段劃分多邊形
2.7凸多邊形的內(nèi)接最大三角形及外切最小三角形
〖〗目錄〖〗〖3〗〖〗〖〗〖2〗〖〗計(jì)算幾何——算法設(shè)計(jì)、分析及應(yīng)用〖〗第3章凸殼及其應(yīng)用
3.1凸殼的基本概念
3.2計(jì)算平面點(diǎn)集凸殼的算法
3.3計(jì)算平面多邊形頂點(diǎn)凸殼的算法
3.4計(jì)算平面多邊形鏈頂點(diǎn)凸殼的算法
3.4.1概念、算法思想與描述
3.4.2解釋與時間復(fù)雜性
3.5計(jì)算平面線段集凸殼的算法
3.6計(jì)算三維空間點(diǎn)集凸殼的算法
3.6.1基本概念
3.6.2Z38算法（三維凸殼）
3.7時間復(fù)雜性低于下界O（nlogn）的凸殼算法
3.8凸殼的應(yīng)用
3.8.1確定任意多邊形的凸、凹頂點(diǎn)
3.8.2利用凸殼求解貨郎擔(dān)問題
3.8.3凸多邊形直徑
3.8.4連接兩個多邊形成一條回路
3.8.5三維空間中平面群的重建
3.8.6構(gòu)造平面曲線
3.8.7某些機(jī)型的識別及其他應(yīng)用
第4章Voronoi圖、三角剖分及其應(yīng)用
4.1Voronoi圖的基本概念
4.2構(gòu)造Voronoi圖的算法
4.2.1Z′41算法（計(jì)算平面點(diǎn)集的Voronoi圖）
4.2.2構(gòu)造最遠(yuǎn)點(diǎn)意義下Voronoi圖的算法
4.3平面點(diǎn)集的三角剖分
4.3.1Delaunay三角剖分與多邊形內(nèi)部點(diǎn)集的三角剖分
4.3.2平面點(diǎn)集三角剖分的算法
4.4平面線段集的三角剖分
4.5平面點(diǎn)線集的三角剖分
4.6平面點(diǎn)集的偽三角剖分
4.7偽三角形的產(chǎn)生
4.8三角剖分的表示
4.9推廣及應(yīng)用
4.9.1最近鄰近
4.9.2最大化最小角的三角剖分
4.9.3最大空圓
4.9.4最小生成樹
4.9.5貨郎擔(dān)問題
4.9.6中軸
4.9.7Voronoi圖與凸殼的關(guān)系
4.9.8Voronoi圖的推廣
4.9.9有約束的Voronoi圖
4.9.10線段集的Voronoi圖
4.9.11關(guān)聯(lián)于多邊形的Voronoi圖
4.9.12點(diǎn)線集的Voronoi圖
4.9.13點(diǎn)、水平、垂直正交線段集的Voronoi圖
4.9.14幾何數(shù)據(jù)壓縮
4.9.15車輛定位導(dǎo)航系統(tǒng)的新定位算法
4.9.16調(diào)色
4.9.17點(diǎn)集增（刪）點(diǎn)之后的三角剖分
4.9.18點(diǎn)云的處理及相關(guān)問題的求解
4.9.19點(diǎn)云曲面邊界線的提取及相關(guān)問題的求解
4.9.20關(guān)聯(lián)于圓的Voronoi圖
4.9.21曲面上點(diǎn)集的三角剖分
4.9.22指紋識別算法
第5章交與并及其應(yīng)用
5.1線段交的算法
5.2多邊形的交
5.2.1凸多邊形交的算法
5.2.2星形多邊形交的算法
5.2.3任意簡單多邊形交的算法
5.3半平面的交及其應(yīng)用
5.3.1半平面的交
5.3.2兩個變量的線性規(guī)劃
5.4多邊形的并
5.5凸多面體的交
5.6應(yīng)用
5.6.1地圖匹配
5.6.2地圖數(shù)據(jù)的處理
5.6.3線段與凸多面體面的交
5.6.4與線段集中線段均相交的直線及其存在區(qū)域
5.6.5特定射線詢問
5.6.6水平、垂直邊多邊形逼近橢圓
5.6.7緊致邊界
5.6.8射線與隱形凸多面體的交
第6章多邊形的獲取及相關(guān)問題
6.1連接不相交線段成簡單多邊形(鏈)
6.2紅外圖像邊緣提取
6.3提取可見光圖像的邊緣
6.4圖像邊界點(diǎn)行排列轉(zhuǎn)換為順序排列
6.5數(shù)字圖像中目標(biāo)邊界的多邊形表示
6.6包含密集點(diǎn)、線集多邊形的獲取
6.7滿足特定條件的多邊形劃分
6.8多邊形與多邊形鏈
6.9圓弧、直線段組成的多邊形頂點(diǎn)凸、凹性的確定
6.10多邊形放大、縮小及移動
6.11帶狀多邊形的處理
6.12下料問題(1)
6.13下料問題（2）
6.14下料問題（3）
6.15線鋸問題(1)
6.16多邊形（鏈）的匹配（1）
6.17多邊形（鏈）的匹配（2）
6.18構(gòu)造凸多邊形
6.19具有屬性點(diǎn)集的控制區(qū)域
6.20多邊形內(nèi)區(qū)域的劃分及多邊形（點(diǎn)集）中心點(diǎn)的確定
6.21滿足一定條件的多邊形劃分(1)
6.22特定條件下凸多邊形的縮小與放大
6.23下料問題（4）
6.24線鋸問題（2）
6.25線鋸問題（3）
6.26線鋸問題（4）
6.27滿足一定條件的多邊形劃分（2）
6.28隱形幾何體（線段、多邊形、長方體）
6.29海洋劃界
第7章幾何體的劃分與等分
7.1平面上不同類型點(diǎn)集的劃分
7.2多邊形內(nèi)不同類型點(diǎn)集的等分
7.3平面上不同類型線段集的劃分
7.4平面上不同類型線段集的等分
7.5平面上不同類型點(diǎn)線集的劃分與等分
7.6鏈、多邊形的劃分與等分
7.7平面上點(diǎn)集劃分的推廣
7.8用圓集劃分平面點(diǎn)集
7.9正方形內(nèi)2k個點(diǎn)的劃分
第8章路徑與回路
8.1最短路徑
8.1.1可視圖及其構(gòu)造
8.1.2Z81算法（尋求網(wǎng)絡(luò)中任意兩點(diǎn)間最短路徑的算法）
8.1.3多面體面上任意兩點(diǎn)之間的最短路徑
8.1.4貨運(yùn)汽車調(diào)度及行駛路徑問題
8.2最短路徑問題的變型
8.3滿足一定條件的運(yùn)動規(guī)劃
8.4多邊形內(nèi)點(diǎn)之間的可視圖
8.5多邊形內(nèi)任意兩點(diǎn)之間的最短路徑
8.6自主車自動定位及確定行車方向
8.7迷宮問題(1)
8.8棋盤上的路徑與回路
8.9選擇道路及判定道路的通過能力
8.10多邊形內(nèi)中心區(qū)域的確定
8.11迷宮問題（2）
8.12網(wǎng)絡(luò)中路徑問題求解的一種搜索方法及回路問題的求解
8.13多邊形集合中任意兩點(diǎn)之間最短路徑（含多邊形數(shù)目最少）
8.14點(diǎn)、多邊形、多面體之間的最短距離
8.15球面上貨郎擔(dān)問題的求解及DNA雙螺旋結(jié)構(gòu)長鏈起源的探索

第9章幾何拓?fù)渚W(wǎng)絡(luò)設(shè)計(jì)
9.1G（S）問題
9.1.1最大間隙問題（MAX G）
9.1.2點(diǎn)集中最大空凸多邊形問題及最大空矩形問題
9.1.3線段集中最大空凸多邊形問題
9.1.4點(diǎn)線集中最大空凸多邊形問題
9.1.5最小覆蓋問題（MIN C）
9.1.6包含平面點(diǎn)集的最小正方形
9.1.7子點(diǎn)集包含問題
9.1.82中心問題
9.1.9k中心問題
9.1.10最近對問題（CPP）
9.1.11所有最近鄰近問題（ANNP）
9.1.12郵局問題（POFP）
9.1.13尋找具有屬性點(diǎn)集的最近點(diǎn)對或點(diǎn)團(tuán)
9.2G（E）問題
9.2.1EMST問題
9.2.2線段集、點(diǎn)線集的最小生成樹
9.2.3直線最小生成樹及其相關(guān)問題
9.2.4由單點(diǎn)或線段端點(diǎn)起始的生成樹
9.2.5歐幾里得最大生成樹問題（EMXT）
9.2.6最小生成網(wǎng)絡(luò)
9.2.7等長線段構(gòu)成網(wǎng)格的變形
9.3G（S，E）問題
9.3.1歐幾里得Steiner最小樹問題（ESMT）
9.3.2直線Steiner最小樹問題（RSMT）
9.3.3求解ESMT問題的算法
9.4G（Ω）問題
9.4.1有障礙物的最大空隙問題（MAX G（Ω））
9.4.2多邊形集中最大空隙問題
9.4.3具有障礙物的歐幾里得最短路徑問題（ESPO）
9.4.4求解E3中ESPO問題的算法
9.4.5具有障礙物的Steiner最小樹問題（ESMTO）
第10章圖形的學(xué)習(xí)、推理及判定
10.1旋轉(zhuǎn)與翻轉(zhuǎn)
10.2圖形的運(yùn)算
10.3對稱性
10.4相似性
10.5不同子域內(nèi)的配對及正多邊形的構(gòu)造
10.6由邊數(shù)、子域數(shù)、子圖位置間關(guān)系等尋找規(guī)則
10.7圖形序列及組合
10.8由圖形組成尋找規(guī)則
10.9通過學(xué)習(xí)及或運(yùn)算尋找規(guī)律
待解決的問題
算法一覽
參考文獻(xiàn)