《計算幾何：算法與套用》是2005年清華大學出版社出版的圖書，作者是（荷蘭）德貝爾赫。
基本介紹
- 書名：計算幾何：算法與套用
- 作者：（荷蘭）德貝爾赫
- ISBN：7302116229、9787302116226
- 頁數：398
- 出版社：清華大學出版社
- 出版時間：2005年9月1日
- 裝幀：平裝
- 開本：16
- 叢書名：套用數學譯叢
內容簡介,目錄,
內容簡介
《計算幾何:算法與套用》(第2版)的前4章對幾何算法進行了討論，包括幾何求交、三角剖分、線性規劃等，其中涉及的隨機算法也是《計算幾何:算法與套用》(第2版)的一個鮮明特點。第5章至第10章介紹了多種幾何結構，包括幾何查找、kd?樹、區域樹、梯形圖、Voronoi圖、排列、Delaunay三角剖分、區間樹、優先查找樹以及線段樹等。第11章至第16章結合實際問題，繼續討論了若干幾何算法及其數據結構，包括高維凸包、空間二分及BSP樹、運動規劃、格線生成及四叉樹、最短路徑查找及可見性圖、單純性區域查找及劃分樹和切分樹等，這些也是對前十章內容的進一步深化。
目錄
第l章 計算幾何：導言
1.1 凸包的例子
1.2 退化及穩健性
1.3 套用領域
1.4 注釋及評論
1.5 習題
第2章 線段求交：專題圖疊合
2.1 線段求交
2.2 雙向連結邊表
2.3 計運算元區域劃分的疊合
2.4 布爾運算
2.5 注釋及評論
2.6 習題
第3章 多邊形三角剖分：畫廊看守
3.1 覆蓋與三角剖分
3.2 多邊形的單調塊劃分
3.3 單調多邊形的三角剖分
3.4 注釋及評論
3.5 習題
第4章 線性規劃：鑄模製造
4.1 鑄造中的幾何
4.2 半平面求交
4.3 遞增式線性規劃
4.4 隨機線性規劃
4.5 無界線性規劃問題
4.6 高維空間中的線性規劃
4.7 最小包圍圓
4.8 注釋及評論
4.9 習題
第5章 正交區域查找：資料庫查詢
5.1 一維區域查找
5.2 kd-樹
5.3 區域樹
5.4 高維區域樹
5.5 一般性點集
5.6 分散層疊
5.7 注釋及評論
5.8 習題
第6章 點定位：找到自己的位置
6.1 點定位及梯形圖
6.2 隨機增量式算法
6.3 退化情況的處理
6.4 尾分析
6.5 注釋及評論
6.6 習題
第7章 Voronoi圖：郵局問題
7.1 定義及基本性質
7.2 構造V0ronoi圖
7.3 注釋及評論
7.4 習題
第8章 排列與對偶：光線跟蹤超採樣
8.1 差異值的計算
8.2 對偶變換
8.3 直線的排列
8.4 層階與偏差
…………
