計算幾何——算法與套用(第2版)

計算幾何——算法與套用(第2版)

《計算幾何——算法與套用(第2版)》是2006年清華大學出版社出版的圖書,作者是鄧俊輝譯。

基本介紹

  • 中文名:計算幾何——算法與套用(第2版)
  • 作者:鄧俊輝
  • 出版社:清華大學出版社
  • 出版時間:2006年4月24日
  • 定價:39.8 元
  • 開本:16 開
  • 裝幀:平裝
  • ISBN:9787302116226
圖書簡介,前言,目錄,

圖書簡介

計算幾何是計算機理論科學的一個重要分支.自20世紀70年代末從算法設計與分析中獨立出來起,不到30年,該學科已經有了巨大的發展,不僅產生了一系列重要的理論成果,也在眾多實際領域中得到了廣泛的套用. 本書的前4章對幾何算法進行了討論,包括幾何求交、三角剖分、線性規劃等,其中涉及的隨機算法也是本書的一個鮮明特點.第5章至第10章介紹了多種幾何結構,包括幾何查找、kd樹、區域樹、梯形圖Voronoi圖、排列、Delaunay三角剖分、區間樹、優先查找樹以及線段樹等.第11章至第16章結合實際問題,繼續討論了若干幾何算法及其數據結構,包括高維凸包、空間二分及BSP樹、運動規劃、格線生成及四叉樹、最短路徑查找及可見性圖、單純性區域查找及劃分樹和切分樹等,這些也是對前十章內容的進一步深化.
本書不僅內容全面,而且緊扣實際套用,重點突出,既有深入的講解,同時每章都設有“注釋及評論”和“習題”,為讀者更深入的理解提供了可能.因此近年來作為教材一直流行於世界眾多大學校園中.我國在計算幾何方面的研究起步較晚,相信本書的出版能對國內此方面教學工作的開展有所推動.

前言

20世紀70年代末,計算幾何從算法設計與分析中孕育而生.今天,它不僅擁有自己的學術刊物和學術會議,而且形成了一個由眾多活躍的研究人員組成的學術群體,因此已經成長為一個被廣泛認同的學科.該領域作為一個研究學科之所以會取得成功,一方面是由於其涉及的問題及其解答本身所具有的美感,另一方面,也是由於在眾多的套用領域(諸如計算機圖形學、地理信息系統和機器人學等)中,幾何算法都發揮了重要的作用.
解決許多幾何問題的早期算法,要么速度很慢,要么難以理解與實現.隨著近年來一些新的算法技術的發展,此前的很多方法都得到了改進與簡化.在這本教材中,我們力圖使這些現代的算法能夠被更廣泛的讀者理解和接受.本書既是面向計算幾何課程的一本教材,同時也可用於自學.
本書的結構.除“導言”外,每一章都從來自套用領域的某一實際問題入手,這個問題將被轉化為一個純粹的幾何問題,並通過計算幾何所提供的方法得到解決.每一章所討論的,實質上就是對應的幾何問題,以及解決該問題所需要的概念與方法.我們根據所希望覆蓋的計算幾何專題,來選取有關的套用;而就具體的套用領域而言,這些介紹還遠遠不夠全面.引入這些套用的目的,只是為了激發讀者的興趣;而各章本身的目的,並不在於為這些問題提供現成可用的解決方法.雖然如此,我們還是認為,為了有效地解決套用中的幾何問題,計算幾何方面的知識是非常重要的.我們希望本書不僅能夠吸引從事算法研究的學者,而且對套用領域的讀者也同樣有所幫助.
同一幾何問題,可能有多種不同的解決方法,不過,在論述大多數幾何問題時,我們將只給出其中一種.我們通常所選取的,都是最易於理解與實現的方法.我們也十分注意,盡力使本書能夠涵蓋更多的方法,比如分治策略、平面掃描以及隨機算法等.對每個問題可能的種種變型,我們也不打算面面俱到;我們覺得,更重要的是首先對計算幾何中的各個主要問題作一介紹,而不是過於深入地去探究少數專題的細枝末節.
某些章的若干節標有星號.這些節的內容涉及解法的改進與擴展,或者解釋了不同問題之間的相互關聯.就對後續章節的理解而言,它們並不十分重要.
每一章的最後,都由名為“注釋及評論”的一節進行概括總結.這些節會給出對應各章所介紹結果的來龍去脈,概述其他的解決方法、一般化處理方法及改進,並給出參考文獻.雖然這些節可以跳過去,但是對於那些希望就某一章的專題作進一步了解的讀者來說,其中的材料都是非常有用的.
每一章的後面,都附有一定數量的習題.其中有些題目旨在檢查讀者對內容的理解程度,也有些題目是對書中內容的推廣,需要精心解答.高難度的問題以及對應於標有星號各節的問題,也被標上星號.
課程大綱.儘管在很大程度上,本書各章之間是相互獨立的,但是在進行介紹時,最好還是不要隨意打亂其次序.例如,第2章介紹了平面掃描算法,故在閱讀採用了這一方法的其他各章之前,最好首先了解該章的內容.出於同樣的考慮,在進入有關隨機算法的各章之前,也應該首先閱讀第4章.
如果是作為計算幾何的第一門課程,我們建議教師按照書中的次序來講授前10章.根據我們的經驗,這10章覆蓋了任何一門計算幾何課程都必須介紹的概念和方法.如果還有可能顧及更多的內容,可以在後面6章中進行挑選.
先修要求.作為教材,本書既適用於高年級本科生的課程,也適用於低年級研究生的課程,具體安排視課程的其他要求而定.讀者應該具備算法設計與分析、數據結構的基本知識:他們必須熟知大O記號,以及諸如排序、二分查找和平衡查找樹等基本的算法技術.讀者不需要對這裡所涉及的套用領域有所了解,也幾乎不需要什麼幾何的知識.在對隨機算法進行分析時,會用到一些非常基本的機率理論.
實現.本書中的算法都是以偽代碼的形式給出,雖略顯概括籠統,但也算詳盡,實現起來相對容易.值得一提的是,我們還嘗試著介紹了處理退化情況的方法,在具體實現過程中如不能解決好這一問題,往往會使整個計畫落空.
我們認為,動手實現其中一個或多個算法將十分有益;這可以令你獲得對算法複雜度的實際感受.每一章都可以當成一個編程訓練的課程項目.根據可利用時間的多少,你既可以只實現算法本身,也可以連同套用系統一起完成.
為了實現一個幾何算法,若干基本的數據類型(點、直線和多邊形等)以及對其實施操作的一些基本例程都是必需的.實現這些基本例程並使之具有穩健性,絕非易事,為此需要投入大量的時間.自己動手這樣做一次不無裨益,然而如果能夠找到一個提供基本數據類型及其操作例程的現成的軟體庫,將很有幫助。
如果您發現了書中的錯誤,或是對本書有什麼建議,也可以通過該頁面與我們聯繫.
關於第2版.第2版與第1版在大部分內容上都是相同的;不同之處主要在於針對一些缺陷進行了修正.原則上,選課的學生依然可以使用第1版.不過那樣的話,應該注意到以下的變動:首先,我們對所有的習題作了仔細的檢查,原先的一些習題已被重新表述或者刪去,同時增添了一些新的習題.其次,第4章和第7章的改動較大——前者對無界線性規劃問題的論述與初版不同,後者有關算法的若干細節也有所改動.

目錄

第1章計算幾何:導言
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.2kd樹
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構造Voronoi圖
7.3注釋及評論
7.4習題
第8章排列與對偶:光線跟蹤超採樣
8.1差異值的計算
8.2對偶變換
8.3直線的排列
8.4層階與偏差
8.5注釋及評論
8.6習題
第9章Delaunay三角剖分:高度插值
9.1平麵點集的三角剖分
9.2Delaunay三角剖分
9.3構造Delaunay三角剖分
9.4分析
*9.5隨機算法框架
9.6注釋及評論
9.7習題
第10章更多幾何數據結構:截窗
10.1區間樹
10.2優先查找樹
10.3線段樹
10.4注釋及評論
10.5習題
第11章凸包:混合物
11.1三維凸包的複雜度
11.2構造三維凸包
*11.3分析
*11.4凸包與半空間求交
*11.5再論Voronoi圖
11.6注釋及評論
11.7習題
第12章空間二分:畫家算法
12.1BSP樹的定義
12.2BSP樹及畫家算法
12.3構造BSP樹
*12.4三維BSP樹的規模
12.5注釋及評論
12.6習題
第13章機器人運動規劃:隨意所之
13.1工作空間與C空間
13.2點機器人
13.3Minkowski和
13.4平移式運動規劃
*13.5允許旋轉的運動規劃
13.6注釋及評論
13.7習題
第14章四叉樹:非均勻格線生成
14.1均勻及非均勻格線
14.2點集的四叉樹
14.3從四叉樹到格線
14.4注釋及評論
14.5習題
第15章可見性圖:求最短路徑
15.1點機器人的最短路徑
15.2構造可見性圖
15.3平移運動多邊形機器人的最短路徑
15.4注釋及評論
15.5習題
第16章單純形區域查找:再論截窗
16.1劃分樹
16.2多層劃分樹
16.3切分樹
16.4注釋及評論
16.5習題
參考文獻
關鍵字索引

相關詞條

熱門詞條

聯絡我們