《計算幾何及套用》是2011年9月1日科學出版社出版的圖書,作者是汪嘉業等。
基本介紹
內容簡介,目錄,
內容簡介
《計算幾何及套用》比較全面地介紹了計算幾何的基本問題、基礎理論和算法。《計算幾何及套用》前12章分別介紹了凸包、Voronoi圖、三角剖分、多邊形剖分、幾何搜尋、相交計算、排列、可見性計算、路徑規劃等基本計算幾何問題和算法,第13、14章則分別探討了若干隨機和並行的計算幾何算法,最後一章給出了關於計算幾何的幾個實際研究和套用中的例子。《計算幾何及套用》在注重介紹計算幾何基礎理論的同時,也注意介紹簡潔、實用和易編程的算法,力求易讀、易懂,並使讀者能夠套用這些理論和算法。為便於消化和理解書中內容,每章末附有習題,以及大量參考文獻。
《計算幾何及套用》可作為高等院校計算機及套用數學等學科的本科生、研究生學習計算幾何的教材,也可作為從事計算幾何研究或套用的其他科技工作者的參考用書。
目錄
前言
第一章 引論
1.1 幾何基礎知識
1.1.1 基本概念
1.1.2 幾何對偶
1.2 算法的複雜度
1.2.1 算法複雜度的度量方法
1.2.2 排序時間複雜度的下界
1.3 數據結構
習題
參考文獻
第二章 二維凸包
2.1 凸包的定義
2.2 極端點和極端邊
2.3 禮品包裹算法
2.4 凸包的快速算法
2.5 Graham算法
2.5.1 基於堆疊的初步算法
2.5.2 算法實現細節的討論
2.5.3 改進的Graham算法
2.6 下限
2.7 增量算法
2.8 分而治之算法
2.8.1 算法描述
2.8.2 算法分析
習題
參考文獻
第三章 凸包擴展
3.1 多面體
3.1.1 引言
3.1.2 正則多面體
3.1.3 多面體的歐拉公式
3.2 三維凸包算法
3.2.1 禮品包裹算法
3.2.2 分而治之算法
3.2.3 增量算法
3.3 簡單多邊形的凸包計算
3.3.1 計算簡單多邊形凸包的局部凸算法
3.3.2 簡單多邊形凸包計算的“陷阱”算法
3.3.3 簡單多邊形凸包的Melkman算法
3.4 凸包的近似算法
3.4.1 凸包的近似算法
3.4.2 二維凸包近似算法精度的討論及其在三維擴展
3.4.3 近似凸包算法的套用
3.5 點集的Maxima
3.6 a-shapes
3.7 點集的相關幾何圖結構
習題
參考文獻
第四章 Voronoi圖
4.1 基本概念
4.2 半平面
4.3 Voronoi圖的基本性質
4.4 Voronoi圖的構造方法
4.4.1 增量法
4.4.2 分而治之法
4.4.3 掃描線法
習題
參考文獻
第五章 廣義Voronoi圖
5.1 加權Voronoi圖
5.1.1 能量圖
5.1.2 加法加權Voronoi圖
5.1.3 乘法加權Voronoi圖
5.1.4 圓與球的Voronoi圖
5.2 高階Voronoi圖
5.2.1 基本概念
5.2.2 基本性質
5.3 最遠點Voronoi圖
5.3.1 基本概念
5.3.2 基本性質
第六章 點集的Delaunay三角剖分
第七章 多邊形剖分
第八章 幾何搜尋
第九章 相交計算
第十一章 可見多邊形與可見圖
第十二章 機器人運動規劃
第十三章 隨機算法第十章 排列
第十四章 並行計算幾何
第十五章 計算幾何研究和套用舉例