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

 第2版前言Ⅴ
 第1版前言Ⅶ
 第0章預(yù)備知識1
 0.1算法與數(shù)據(jù)結(jié)構(gòu)2
 0.1.1算法2
 0.1.2數(shù)據(jù)結(jié)構(gòu)5
 0.2相關(guān)的幾何知識9
 0.2.1基本定義9
 0.2.2線性變換群下的不變量11
 0.2.3幾何對偶性12
 0.3計算模型13
 第1章幾何查找(檢索)17
 1.1點定位問題18
 1.1.1點q是否在多邊形P內(nèi)19
 1.1.2確定點q在平面剖分中的位置24
 1.1.3Z1-3算法30
 1.2范圍查找問題31
 1.2.1多維二叉樹(kD樹)的方法32
 1.2.2直接存取方法34
 1.2.3范圍樹方法36
 1.3判定點集是否在多邊形內(nèi)37
 1.4平面網(wǎng)絡(luò)的處理與點q的定位39
 第2章多邊形43
 2.1凸多邊形43
 2.2簡單多邊形49
 2.3多邊形的三角剖分54
 2.4多邊形的凸劃分58
 2.5連接不相交線段成簡單多邊形(鏈)66
 2.6下料問題71
 2.7紅外圖像邊緣提取79
 2.8滿足特定條件的多邊形劃分84
 2.9多邊形與多邊形鏈87
 2.10圓弧. 直線段組成的多邊形頂點凸. 凹性的確定90
 2.11多邊形放大. 縮小及移動91
 2.12帶狀多邊形的處理93
 第3章凸殼及其應(yīng)用96
 3.1凸殼的基本概念96
 3.2計算平面點集凸殼的算法100
 3.2.1卷包裹法100
 3.2.2格雷厄姆方法101
 3.2.3分治算法102
 3.2.4Z3-1算法與Z3\|2算法104
 3.2.5實時凸殼算法107
 3.2.6增量算法111
 3.2.7近似凸殼算法112
 3.3計算平面多邊形頂點凸殼的算法112
 3.4計算平面多邊形鏈頂點凸殼的算法116
 3.4.1概念. 算法思想與描述116
 3.4.2解釋與時間復(fù)雜性119
 3.5計算平面線段集凸殼的算法120
 3.6計算三維空間點集凸殼的算法128
 3.6.1基本概念128
 3.6.2卷包裹法129
 3.6.3分治算法131
 3.6.4Z3\|8算法133
 3.6.5增量算法134
 3.7凸殼的應(yīng)用135
 3.7.1確定任意多邊形的凸. 凹頂點135
 3.7.2利用凸殼求解貨郎擔問題138
 3.7.3凸多邊形直徑140
 3.7.4連接兩個多邊形成一條回路143
 第4章Voronoi圖. 三角剖分及其應(yīng)用146
 4.1Voronoi圖的基本概念147
 4.2構(gòu)造Voronoi圖的算法151
 4.2.1半平面的交151
 4.2.2增量構(gòu)造方法151
 4.2.3分治法155
 4.2.4減量算法157
 4.2.5平面掃描算法158
 4.2.6構(gòu)造最遠點意義下Voronoi圖的算法160
 4.3平面點集的三角剖分162
 4.3.1平面點集三角剖分的貪心算法162
 4.3.2Delaunay三角剖分與多邊形內(nèi)部點集的三角剖分164
 4.3.3平面點集三角剖分的算法166
 4.4平面線段集的三角剖分172
 4.5平面點線集的三角剖分176
 4.6應(yīng)用181
 4.6.1最近鄰近181
 4.6.2最大化最小角的三角剖分182
 4.6.3最大空圓182
 4.6.4最小生成樹186
 4.6.5貨郎擔問題188
 4.6.6中軸188
 4.6.7Voronoi圖與凸殼的關(guān)系195
 4.6.8Voronoi圖的推廣198
 4.6.9有約束的Voronoi圖206
 4.6.10幾何數(shù)據(jù)壓縮207
 4.6.11車輛定位導(dǎo)航系統(tǒng)的新定位算法211
 4.6.12調(diào)色214
 4.6.13點集增(刪)點之后的三角剖分215
 第5章交與并及其應(yīng)用217
 5.1線段交的算法217
 5.2多邊形的交224
 5.2.1凸多邊形交的算法224
 5.2.2星形多邊形交的算法228
 5.2.3任意簡單多邊形交的算法230
 5.3半平面的交及其應(yīng)用232
 5.3.1半平面的交232
 5.3.2兩個變量的線性規(guī)劃233
 5.4多邊形的并239
 5.5凸多面體的交245
 5.6應(yīng)用249
 5.6.1地圖匹配249
 5.6.2地圖數(shù)據(jù)的處理254
 5.6.3線段與凸多面體面的交254
 第6章矩形幾何256
 6.1判定垂直. 水平線段是否相交的算法256
 6.2矩形幾何問題的特征及解決問題的途徑258
 6.3矩形并的面積與周長259
 6.4矩形并的輪廓262
 6.5矩形并的閉包266
 6.6矩形并的非平凡輪廓和外輪廓269
 6.7矩形的交271
 6.8應(yīng)用舉例274
 第7章幾何體的排列276
 7.1基本概念276
 7.2確定直線排列的算法280
 7.3對偶性282
 7.4Voronoi圖286
 7.4.1一維情況286
 7.4.2二維情況288
 7.5應(yīng)用289
 7.5.1k-最近鄰近289
 7.5.2刪去隱藏面289
 7.5.3特征圖290
 7.5.4點集的分割291
 第8章算法的運動規(guī)劃294
 8.1最短路徑295
 8.1.1可視圖及其構(gòu)造295
 8.1.2Z8-1算法296
 8.1.3多面體面上任意兩點之間的最短路徑301
 8.1.4貨運汽車調(diào)度及行駛路徑問題308
 8.2移動圓盤309
 8.3平移凸多邊形310
 8.4移動桿狀機器人313
 8.4.1網(wǎng)格分解315
 8.4.2收縮方法317
 8.5機器人臂的運動319
 8.5.1可達性319
 8.5.2構(gòu)造可達性321
 8.6可分離性324
 8.6.1多種可分離性324
 8.6.2借助于平移的可分離性325
 8.6.3分離問題是NP難的326
 8.6.4模擬河內(nèi)塔問題326
 8.7滿足一定條件的運動規(guī)劃327
 第9章幾何拓撲網(wǎng)絡(luò)設(shè)計329
 9.1G(S)問題330
 9.1.1最大間隙問題(MAX G)331
 9.1.2最小覆蓋問題(MIN C)333
 9.1.32-中心問題337
 9.1.4k-中心問題341
 9.1.5最近對問題(CPP)349
 9.1.6所有最近鄰近問題(ANNP)350
 9.1.7郵局問題(POFP)351
 9.2G(E)問題352
 9.2.1EMST問題353
 9.2.2歐幾里得TSP355
 9.2.3歐幾里得最大生成樹問題(EMXT)356
 9.3G(S, E)問題357
 9.3.1歐幾里得Steiner最小樹問題(ESMT)358
 9.3.2直線Steiner最小樹問題(RSMT)361
 9.4G(Ω)問題362
 9.4.1有障礙物的最大空隙問題(MAX G(Ω))363
 9.4.2具有障礙物的歐幾里得最短路徑問題(ESPO)364
 9.4.3具有障礙物的Steiner最小樹問題(ESMTO)366
 第10章隨機幾何算法與并行幾何算法371
 10.1分類和搜索線性表的隨機算法372
 10.1.1隨機二叉樹373
 10.1.2跳越表376
 10.2增量算法378
 10.2.1四邊形分解378
 10.2.2凸多胞形382
 10.2.3Voronoi圖386
 10.2.4構(gòu)形空間388
 10.3動態(tài)算法391
 10.4隨機抽樣395
 10.4.1具有限界的構(gòu)形空間396
 10.4.2頂-向下的抽樣397
 10.4.3底-向上的抽樣399
 10.4.4動態(tài)抽樣401
 10.5并行幾何算法403
 10.5.1凸殼問題407
 10.5.2排列與分解408
 10.5.3鄰近410
 10.5.4幾何搜索410
 10.5.5可視性和最優(yōu)化411
 待解決的問題413
 算法索引415
 參考文獻420
</font>