算法設計與分析第四版(周培德)

算法設計與分析pdf是由周培德編寫的計（jì）算幾何係（xì）列的第（dì）四版圖（tú）書，采用了周培德算法來演繹幾何相關的知識和問題（tí），讓大家更好的掌握學習方法和解題技巧，綠色資源（yuán）網誠意推薦！

計算幾何：算法設計與分析（第4版）目錄

第0章預備知（zhī）識

0.1算法與數據結構

0.1.1算法

0.1.2數據結構

0.2相關的幾（jǐ）何知識

0.2.1基本定義

0.2.2線性變換群下的不變量

0.2.3幾何對偶性

0.3計算模型

第（dì）1章幾何（hé）查找(檢索)

1.1點定位問題

1.1.1點□是否在（zài）多（duō）邊形P內

1.1.2確定點□在平（píng）麵剖分中的位置（zhì）

1.1.3Z□算法(判定點q在哪個三角形的算法)

1.2判定點集是否在多邊形內

1.3平麵網絡的處理與點q的定位

1.4平麵上鏈的處理與點（diǎn）q的定位

1.5平麵上線段的處理與點q的定位

1.6判定點是否在多（duō）邊形內部的新算法

第2章多邊形

2.1凸多邊（biān）形

2.2簡單（dān）多邊（biān）形

2.3多邊形的三角（jiǎo）剖分

2.4多邊形的凸劃分

2.5對多邊（biān）形鏈的監視（shì）

2.6線段（duàn）劃分多邊（biān）形（xíng）

2.7凸多（duō）邊形的內接最大三角形及外切最（zuì）小三角形

第3章凸殼及其應用

3.1凸殼的基本概念

3.2計算平麵點集凸殼的算法（fǎ）

3.3計算平麵多（duō）邊形頂點凸（tū）殼的算法

3.4計算平麵多邊形鏈頂點凸殼的算法

3.4.1概念、算法思想與描述

3.4.2解釋與（yǔ）時（shí）間複雜性（xìng）

3.5計算平麵線段集凸殼的算法

3.6計算三維空（kōng）間點集凸殼的算（suàn）法

3.6.1基本概念

3.6.2Z粥算（suàn）法(三維凸殼)

3.7時間複（fù）雜性低於下界O(nlogn)的凸殼算法

3.8凸殼的應用

3.8.1確定任意多邊形的（de）凸、凹頂點

3.8.2利用（yòng）凸殼求解貨郎擔問題（tí）

3.8.3凸多邊形（xíng）直（zhí）徑（jìng）

3.8.4連（lián）接兩個多（duō）邊形成一條回路

第4章Voronoi圖、三角剖分及其應用

4.1Voronoi圖（tú）的基本概念

4.2構造Voronoi圖的算法

4.2.1z□算法(計算平麵點集的Voronoi圖)

4.2.2構造最（zuì）遠點意義下Voronoi圖的（de）算法

4.3平麵點集的三角剖（pōu）分

4.3.1Delaunay三（sān）角剖分（fèn）與多邊（biān）形（xíng）內部點集的三角剖分

4.3.2平（píng）麵點集三角剖分的算法

4.4平麵線段集的三角剖分

4.5平麵點（diǎn）線集的三角剖分

4.6平麵點集的偽三角剖分

4.7偽三角形的產生

4.8三角剖分的表示

4.9推廣及應用

4.9.1最近鄰近

4.9.2最（zuì）大化最小角的三角剖分

4.9.3最大空圓

4.9.4最小生成樹

4.9.5貨郎擔問（wèn）題

4.9.6中軸

4.9.7Voronoi圖（tú）與凸殼的關係

4.9.8Voronoi圖（tú）的推廣

4.9.9有約束（shù）的Voronoi圖

4.9.10線段集的Voronoi圖

4.9.11關聯（lián）於多邊形的Voronoi圖

4.9.12點線集的Voronoi圖（tú）

4.9.13點、水（shuǐ）平、垂直正交線段集的Voronoi圖

4.9.14幾何數據壓縮

4.9.15車輛定（dìng）位導航係統的新定位算（suàn）法

4.9.16調色

4.9.17點集增(刪)點之後的三角（jiǎo）剖分

第5章交（jiāo）與並及其應用

5.1線段交（jiāo）的算法

5.2多邊形的交

5.2.1凸多邊形（xíng）交的算法

5.2.2星形多邊形交的（de）算法

5.2.3任意簡單多邊形交的算法（fǎ）

5.3半平麵的交（jiāo）及其應用

5.3.1半平麵的交

5.3.2兩個變量的（de）線性規劃

5.4多邊形的並

5.5凸多麵體的交

5.6應用

5.6.1地圖匹配

5.6.2地圖數據的處理

5.6.3線（xiàn）段與凸多麵體麵的（de）交

5.6.4與線（xiàn）段集中線段均相交的直線及其存在區域

5.6.5特定射線（xiàn）詢問（wèn）

第6章多邊形的獲取及相關問題

6.1連接不相交線段成簡單多邊形(鏈)

6.2紅外圖像邊（biān）緣提取（qǔ）

6.3提（tí）取（qǔ）可見光圖像的邊緣

6.4圖像邊界（jiè）點行排列轉換（huàn）為順序排列

6.5數字圖像（xiàng）中目標邊界的多邊形表示

6.6包含密（mì）集點、線集多邊形的獲取

6.7滿（mǎn）足特定條（tiáo）件的多邊形劃分

6.8多邊形（xíng）與多邊形鏈

6.9圓弧、直線段（duàn）組成的多（duō）邊形頂點凸、凹性的確定

6.10多邊形放大、縮（suō）小（xiǎo）及（jí）移動

6.11帶狀多邊形的處理

6.12下料問題(1)

6.13下料問題（tí）(2)

6.14下料問題(3)

6.15線（xiàn）鋸問題（tí）

6.16多邊形(鏈)的匹配(1)

6.17多邊形(鏈)的匹配(2)

6.18構造凸（tū）多邊形

6.19具有屬（shǔ）性點集的控製區域

6.20多邊形內區域的劃分及多（duō）邊形(點集)中心點的確定

6.21滿足一定條（tiáo）件的多邊形劃（huá）分

6.22特（tè）定條件下凸多邊形的縮小與（yǔ）放大

第7章（zhāng）幾何體的（de）劃分與等分

7.1平麵上不同類型（xíng）點集的劃分

7.2多邊形（xíng）內不同類型（xíng）點集的等（děng）分（fèn）

7.3平麵上（shàng）不同類型（xíng）線段集的（de）劃分（fèn）

7.4平麵上不（bú）同類型線段集的（de）等分

7.5平麵上不同類型點線集的劃分與等分

7.6鏈、多邊形的劃分與等分

第8章路徑與回路

8.1最短（duǎn）路（lù）徑

8.1.1可視圖及其構造

8.1.2Z□算法(尋求網絡中任（rèn）意兩點（diǎn）間最短（duǎn）路徑的算法

8.1.3多麵體麵上任意兩點之間的（de）最短（duǎn）路徑

8.1.4貨運汽車調度及行駛路徑問題

8.2最短路徑問題的變型

8.3滿足一定條件的運動規劃

8.4多邊形內點之間的可視圖

8.5多邊形內（nèi）任意兩點之間的最短路徑

8.6自主車自動定位及確定行車方向

8.7迷宮問題

8.8棋盤上的路（lù）徑與回路

8.9選擇道路及判定道路的通過（guò）能力

8.10多邊形內中心區域（yù）的確定

第9章幾何拓撲網（wǎng）絡設計

9.1G(S)問題

9.1.1最大間隙問題(MAXG)

9.1.2點集（jí）中最大空凸多（duō）邊形問題及最（zuì）大（dà）空矩形問題

9.1.3線（xiàn）段集中最大空凸多邊形問題

9.1.4點線集中最大空凸多邊形問題（tí）

9.1.5最小覆蓋問題(MINC)

9.1.6包含平麵點集的最小正方形（xíng）

9.1.7子點集包含問題

9.1.82-中心問題

9.1.9k-中心問題

9.1.10最（zuì）近對問題(CPP)

9.1.11所有最近鄰近問（wèn）題(ANNP)

9.1.12郵（yóu）局問題(POFP)

9.1.13尋找具有屬性點集的最近點對（duì）或點（diǎn）團

9.2G(E)問題

9.2.1EMST問（wèn）題

9.2.2線段集、點線集的最小生成樹

9.2.3直線最小生成樹及其相關問題

9.2.4歐幾裏得TSP

9.2.5歐幾裏得最大生成樹問題(EMXT)

9.2.6最小生成網絡

9.3G(S，E)問題

9.3.1歐幾裏得Steiner最小樹問題(ESMT)

9.3.2直線Steiner最小樹問題(RSMT)

9.3.3求解ESMT問題（tí）的算法

9.4G(□)問（wèn）題

9.4.1有障礙物的（de）最大空隙問題(MAXG(□)

9.4.2多邊形集中（zhōng）最大（dà）空（kōng）隙問題

9.4.3具有障礙物的歐幾裏得（dé）最短路徑問題(ESPO)

9.4.4求（qiú）解E3中（zhōng）ESPO問題的算法

9.4.5具有障礙物（wù）的Steiner最小樹問題(ESMTO)

待解決的問題

算法一覽

參考（kǎo）文獻

名（míng）詞索引（yǐn）

算法設（shè）計與分析周培德（dé）圖書介（jiè）紹

《計算幾何：算法設（shè）計與分析（第4版）》係統地介紹了計算（suàn）幾何中的基本概念、求解諸多問題的算法及複雜性分析（xī），概括了求解幾何問題所特有的許多思想方（fāng）法（fǎ）、幾何結構與數據結構（gòu）。全書共分10章，包（bāo）括：預備知識，幾何查找（檢索），多（duō）邊形，凸殼及其應用，Voronoi圖、三角剖分及（jí）其應用，交與並及其應用，多邊形的（de）獲（huò）取及相關問題，幾何體的劃分（fèn）與等分，路徑與回路，幾何拓撲網絡（luò）設計等。 《計算幾何：算法設計與分析（第4版）》可作為高等院校計算（suàn）機、自動化等（děng）專業研究生或本科（kē）高年級學生的教材或教學（xué）參考書，也可供軟件開發人員、相關專業科（kē）技工作者參考。