計算幾何：算法與套用（第3版）

圖書簡介

20世紀70年代末，計算幾何學（computationalgeometry）從算法設計與分析中孕育而生。今天，它不僅擁有自己的學術刊物和學術會議，而且形成了一個由眾多活躍的研究人員組成的學術群體，因此已經成長為一個被廣泛認同的學科。該領域作為一個研究學科之所以會取得成功，一方面是由於其涉及的問題及其解答本身所具有的美感，而另一方面，也是由於在（諸如計算機圖形學、地理信息系統和機器人學等）眾多的套用領域中，幾何算法都發揮了重要的作用。

圖書目錄

前言 I

1 ?計算幾何：導言 1

1.1 凸包的例子 2

1.2 退化及魯棒性 9

1.3 套用領域 10

1.3.1 計算機圖形學 10

1.3.2 機器人學 11

1.3.3 地理信息系統 11

1.3.4 CAD/CAM 12

1.3.5 其他套用領域 12

1.4 注釋及評論 13

習題 15

2 ?線段求交：專題圖疊合 19

2.1 線段求交 20

2.2 雙向連結邊表 30

2.3 計運算元區域劃分的疊合 34

2.4 布爾運算 41

2.5 注釋及評論 42

習題 43

3 ?多邊形三角剖分：畫廊看守 47

3.1 看守與三角剖分 48

3.2 多邊形的單調塊劃分 52

3.3 單調多邊形的三角剖分 59

3.4 注釋及評論 63

習題 64

4 ?線性規劃：鑄模製造 67

4.1 鑄造中的幾何 68

4.2 半平面求交 70

4.3 遞增式線性規劃 75

4.4 隨機線性規劃 81

4.5 無界線性規劃問題 84

4.6* 高維空間中的線性規劃 87

4.7* 最小包圍圓 91

4.8 注釋及評論 95

習題 96

5 ?正交區域查找：資料庫查詢 99

5.1 一維區域查找 100

5.2 kd-樹 103

5.3 區域樹 109

5.4 高維區域樹 113

5.5 一般性點集 115

5.6* 分散層疊 116

5.7 注釋及評論 119

習題 121

6 ?點定位：找到自己的位置 125

6.1 點定位及梯形圖 126

6.2 隨機增量式算法 132

6.3 退化情況的處理 141

6.4* 尾分析 143

6.5 注釋及評論 147

習題 148

7 ? Voronoi圖：郵局問題 151

7.1 定義及基本性質 152

7.2 構造Voronoi圖 156

7.3 線段集Voronoi圖 165

7.4 最遠點Voronoi圖 169

7.5 注釋及評論 173

習題 175

8 ?排列與對偶：光線跟蹤超採樣 179

計算幾何：算法與套用（第3版）

基本介紹

圖書簡介

圖書目錄

相關詞條

熱門詞條