計算幾何
出版時間：2005-9 出版社：清華大學 作者：Mark de Berg,Otfried Cheong,Marc van Kreveld,Mark Overmars 頁數：398 字數：554000 譯者：鄧俊輝
Tag標簽：無
內容概要
計算幾何是計算機理論科學的一個重要分支。自20世紀70年代末從算法設計與分析中獨立出來起，不到30年，該學科已經有了巨大的發(fā)展，不僅產生了一系列重要的理論成果，也在眾多實際領域中得到了廣泛的應用。 本書的前4章對幾何算法進行了討論，包括幾何求交、三角剖分、線性規(guī)劃等，其中涉及的隨機算法也是本書的一個鮮明特點。第5章至第10章介紹了多種幾何結構，包括幾何查找、kd?樹、區(qū)域樹、梯形圖、Voronoi圖、排列、Delaunay三角剖分、區(qū)間樹、優(yōu)先查找樹以及線段樹等。第11章至第16章結合實際問題，繼續(xù)討論了若干幾何算法及其數據結構，包括高維凸包、空間二分及BSP樹、運動規(guī)劃、網格生成及四叉樹、最短路徑查找及可見性圖、單純性區(qū)域查找及劃分樹和切分樹等，這些也是對前十章內容的進一步深化。 本書不僅內容全面，而且緊扣實際應用，重點突出，既有深入的講解，同時每章都設有“注釋及評論”和“習題”，為讀者更深入的理解提供了可能。因此近年來作為教材一直流行于世界眾多大學校園中。我國在計算幾何方面的研究起步較晚，相信本書的出版能對國內此方面教學工作的開展有所推動。
書籍目錄
第1章 計算幾何：導言 1.1 凸包的例子 1.2 退化及穩(wěn)健性 1.3 應用領域 1.4 注釋及評論 1.5 習題第2章 線段求交：專題圖疊合 2.1 線段求交 2.2 雙向鏈接邊表 2.3 計算子區(qū)域劃分的疊合 2.4 布爾運算 2.5 注釋及評論 2.6 習題第3章 多邊形三角剖分：畫廊看守 3.1 覆蓋與三角剖分 3.2 多邊形的單調塊劃分 3.3 單調多邊形的三角剖分 3.4 注釋及評論 3.5 習題第4章 線性規(guī)劃：鑄模制造 4.1 鑄造中的幾何 4.2 半平面求交 4.3 遞增式線性規(guī)劃 4.4 隨機線性規(guī)劃 4.5 無界線性規(guī)劃問題 *4.6 高維空間中的線性規(guī)劃 *4.7 最小包圍圓 4.8 注釋及評論 4.9 習題第5章 正交區(qū)域查找：數據庫查詢 5.1 一維區(qū)域查找 5.2 kd?樹 5.3 區(qū)域樹 5.4 高維區(qū)域樹 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.2 Delaunay三角剖分 9.3 構造Delaunay三角剖分 9.4 分析 *9.5 隨機算法框架 9.6 注釋及評論 9.7 習題第10章 更多幾何數據結構：截窗 10.1 區(qū)間樹 10.2 優(yōu)先查找樹 10.3 線段樹 10.4 注釋及評論 10.5 習題第11章 凸包： 混合物 11.1 三維凸包的復雜度 11.2 構造三維凸包 *11. 3分析 *11.4 凸包與半空間求交 *11.5 再論Voronoi圖 11.6 注釋及評論 11.7 習題第12章 空間二分：畫家算法 12.1 BSP樹的定義 12.2 BSP樹及畫家算法 12.3 構造BSP樹 *12.4 三維BSP樹的規(guī)模 12.5 注釋及評論 12.6 習題第13章 機器人運動規(guī)劃：隨意所之 13.1 工作空間與C空間 13.2 點機器人 13.3 Minkowski和 13.4 平移式運動規(guī)劃 *13.5 允許旋轉的運動規(guī)劃 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章 單純形區(qū)域查找：再論截窗 16.1 劃分樹 16.2 多層劃分樹 16.3 切分樹 16.4 注釋及評論 16.5 習題參考文獻關鍵詞索引
圖書封面
圖書標簽Tags
無
評論、評分、閱讀與下載
用戶評論 (總計37條)
- 這是一本很好的計算幾何方面的書，本書雖然沒有附帶源代碼，雖然是翻譯過來的，但是對算法還是講解得比較清晰！計算幾何的算法有些不易理解，需要反復閱讀、思考！這本書是一本難得的參考！
- 計算幾何——算法與應用
有的東西看不懂 慢慢看吧 - 書寫得不錯，涉及了重要的計算幾何的概念。而且講解細致，深入淺出。由具體事例引出，抽象概括出一般結論。最后還給出了參考注解，為更深入的理解提供了便利。
- 我平時總是很懶得去寫評論，但看了這本書之后真的覺得有必要來寫一寫，希望真的需要這本書的朋友可以及時地找到它。每一個章節(jié)都以一個很實用的例子作為引子，都有很詳實的解決方案，而且是由淺入深，層層遞進。最讓我覺得感動得是全書370頁的正文，引文數達到了330個，即使沒有解決的問題也會給我們指出去什么地方可以找答案。我也非常感謝看過這本書的朋友給出的建議，讓我找到了這本書
- 對NOI很有幫助，建議先看高級數據結構，再看此書。
- 從事計算機圖形處理人員必備的參考書，尤其是做研究的．
- 內容全面具體
- 很不錯的一本書，講的很詳細
- 相當好的一本書，翻譯質量也不錯，就是需要一定的邏輯能力哦，哈哈，向困難出發(fā)。。。
- 易懂 適合入門
- 印刷很好，還沒有看完。
- 但是很喜歡
- 不錯，有點難
- 的確是一本難得的好書~~
- 相當好,受益頗多
- 非常好的書。。。支持。
- 樹種介紹了各種算法以及應用，但卻是還是需要一定的數學基礎，開卷有益吧
- 書寫的比較歐美風格，不過表述不是很容易理解，而且有時候可能是沒法理解。譯者很多時候都得加上“譯者注”。內容介紹的比較多，而且比較全面。唯一的缺陷就是，在當當上買了書，結果少頁重頁了，換了后還是那個毛病。
- 讀這本書讓我受益匪淺！盼望已久的好書！
- 書不錯，速度很慢！
- 送書的速度和質量都挺好的
- 不可多得好書，寫的很簡單明了，推薦數學系的做軟件開發(fā)看看~
- 感覺理論性有點強，不過周培德的那本好
- 怎么做Delauny三角剖分？里面步驟非常清晰和理。好像是一個老師手把手地教。而且這章用的不是舊的1985年divide-conquer方法，而是新的1992年的randomized incremental方法.
- 這本書是給研究生級別的學生讀的. 這書不知為什么比較難懂. 可能是我自己的問題. 我認識的數學系的人感覺這書讀起來很怪, 計算機系的也感覺有點難理解. 如果發(fā)現讀的有壓力, 推薦也可以看看Joseph O'Rourke的computational geometry in C.(中國有影印版, 很便宜的...)
第一次讀這書是9年級的時候. 那時候實力完全看不懂只好放棄. (表示那時候我讀concrete mathematics也沒有那么吃力)
第二次讀就是大一的時候在Stony Brook上Joseph Mitchell的Computational geometry的課程. 這一次我終于可以看懂這書了. 這時我已經解決過一個基礎的算法課程, 但是這里面的一些內容還是給了我一堆nerdgasm.
我第一次真正的analyze一個randomized algorithm.
學習了一堆data structure kd-tree, range tree, interval tree. 還有一些神奇的加速算法的招數, 如fractional cascading(只有l(wèi)og(n)的加速...真蛋痛, 不過可以用來improve theoretical bounds).
學到了如何O(n)的空間, O(log(n))做point location. 這個的讓我orz的內容.
這兩部分真的很有用, 有時發(fā)現很多問題都能轉換成為point location或者range query.
曾經看過點projective geometry, 應該是比較熟悉duality的... 但是看到這本書里面的duality, 才發(fā)現這有多么的有用. Mitchell告訴我們, 在發(fā)現duality之前, 1個問題都會弄出兩個paper出來, 一個是paper, 一個是dual paper. 哈哈哈哈哈(真冷...)
Art gallery theory的證明, 竟然用了graph theory. 實際上CG里面還有不少其他可以用到graph theory的東西. 這是我感覺很有意思的部分.
習題真的非常精彩啊. 我想分享我曾今做的一個題. 由于我是和作業(yè)一起做的, 所以以下這題可能并不存在于書上.
給藍色和紅色的點n個. 是否存在一個圓, 使得所有的藍點在圓的內部, 所有的紅點在圓的外部呢?
我當時想了很久, 似乎弄出了超級復雜的O(n log n)的用到Delaunay triangulation的算法...現在記不得了... 我和一個我喜歡的女生說過"你做出這題一定要給我打個電話哦." 我現在還在等待...
實際上有一個O(n)的算法.
還有一題, 是我做TA的時候, 交給本科生做的.
假如art gallery里面的guard可以看到反射k次的光, (光的反射就是入射角=反射角. 如果射到一個vertex, 光就被吸收). Art gallery theorem會怎么改變呢? (剛開始看答案似乎滿難, 后來發(fā)現蠻簡單的)
Open Problem:
如果可以看到反射無限次的光, art gallery theorem又會有什么改變呢? - 這本書是我導師推薦的，作本科畢業(yè)設計的課題就是做range search tree的data structure。后來讀了其他部分，也很有意思。由淺入深的一些算法。書不厚，讀起來沒有壓力
- 因為上課， 這本書當時也算仔仔細細看了大半了。
如果現在讓我來回憶 這本書講了什么？ 我能記得的只有幾個算法思想： amortized algorithm， sweeping line， randomly increamenting, divide and conquer, 以及想讓人破腦袋的無數習題。
一些復雜的數據結構， 例如voronoi diagram的建立或者是判斷l(xiāng)ine segment intersection都要用sweeping line algorithm及其變種， 所有點都看作event， sweeping動態(tài)維持一個BST和queue來操作訪問到的event。
randomly incrementing也是很惡搞的一個東西，和greedy一樣， 想法簡單， 證明復雜。 比如找一堆線段圍成convex hull的最低點， 或者是建造farthest voronoi diagram， 或者是構造在平面投影是convex hull的三維convex hull， 這個算法說明了你先構造好n-1的case， 然后用期望是常數時間的代價再構造n的case。這樣， 期望代價是O(n）， 而不是1+2+3+...+n=O(n^2)
amortized 就更有用了，且看Timothy 的那個convex hull算法是如何被人簡化的。 另外， Timothy的那個convex hull 算法和quick selection算法異曲同工， 都是把問題劃分為K個小問題， 然后加起來發(fā)現時間復雜度還相當低。
此外， 這本書上還有一大堆空間數據結構， 比如Kd-Tree啊， Range Tree， 里面充斥著奇技淫巧， 怎樣用更少的空間存儲， 怎樣搜索簡化， 用什么數組維護， 什么樣的query用什么樣數據結構好？ 這些結構在高維空間又是啥情況？
計算幾何里真正有些幾何美感的東西就是兩個具有對偶dual性質的幾何結構了， 點和線， convex hull 與half plane intersection， Voronoi diagram和Delauney triangulation， dual的好處是一個東西你弄不懂， 可以轉而想另外一個更直觀的問題。
計算幾何真是一個大坑， 里面各個算法充斥著畸形的退化情況， 看懂一個算法就累得半死， 更不用說要仔細地實現。 有許多特殊情況要考慮， 而且據稱很多特殊情況比原始問題要難得多， 往往要構造特殊的算法。 這本書不愧是一本入門教材， 沒有把這么bt的例子展示給我。
- j. mitchell 是你們學校的吧 今年 Godel 獎得主
另外 Ker-I Ko 好像也是 - 沒錯...
- 給藍色和紅色的點n個. 是否存在一個圓, 使得所有的藍點在圓的內部, 所有的紅點在圓的外部呢?
這個是Vapnik–Chervonenkis dimension的問題哦，可愛。 - 不一樣的 VC theory保證一定條件下點集的所有子集都能被classify 這里是設計算法處理某個子集
- 這幾天在聽Jie Gao講這本書……
- hmm. 這個信息可以讓我有途徑得知你的大學呢...
- 得知我的大學居然還需要這種信息，你信息搜索能力不夠好啊~~
- ...的確...
我還是不知道你哪個大學的.- -
要等下學期非常小心的"無意"問起Gao暑假在干什么... - 9年級就在看具體數學，我勒個去。我9年級的時候除了高中數學課本什么數學書都木有，十年級的時候才開始學微積分，可惜之后的六年數學水平一直處于退步階段。
- 這篇評論寫的真好啊。順便說下，那個circle separability sariel har-peled的notes里有講。