计算几何

出版时间：2005-9  出版社：清华大学  作者：Mark de Berg,Otfried Cheong,Marc van Kreveld,Mark Overmars  页数：398  字数：554000  译者：邓俊辉  
Tag标签：无  

内容概要

计算几何是计算机理论科学的一个重要分支。自20世纪70年代末从算法设计与分析中独立出来起，不到30年，该学科已经有了巨大的发展，不仅产生了一系列重要的理论成果，也在众多实际领域中得到了广泛的应用。    本书的前4章对几何算法进行了讨论，包括几何求交、三角剖分、线性规划等，其中涉及的随机算法也是本书的一个鲜明特点。第5章至第10章介绍了多种几何结构，包括几何查找、kd?树、区域树、梯形图、Voronoi图、排列、Delaunay三角剖分、区间树、优先查找树以及线段树等。第11章至第16章结合实际问题，继续讨论了若干几何算法及其数据结构，包括高维凸包、空间二分及BSP树、运动规划、网格生成及四叉树、最短路径查找及可见性图、单纯性区域查找及划分树和切分树等，这些也是对前十章内容的进一步深化。    本书不仅内容全面，而且紧扣实际应用，重点突出，既有深入的讲解，同时每章都设有“注释及评论”和“习题”，为读者更深入的理解提供了可能。因此近年来作为教材一直流行于世界众多大学校园中。我国在计算几何方面的研究起步较晚，相信本书的出版能对国内此方面教学工作的开展有所推动。

书籍目录

第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.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 构造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 区间树  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.1 BSP树的定义  12.2 BSP树及画家算法  12.3 构造BSP树  *12.4 三维BSP树的规模  12.5 注释及评论  12.6 习题第13章 机器人运动规划：随意所之  13.1 工作空间与C空间  13.2 点机器人  13.3 Minkowski和  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 习题参考文献关键词索引

用户评论 (总计37条)

•   这是一本很好的计算几何方面的书，本书虽然没有附带源代码，虽然是翻译过来的，但是对算法还是讲解得比较清晰！计算几何的算法有些不易理解，需要反复阅读、思考！这本书是一本难得的参考！
•   计算几何——算法与应用
  
  有的东西看不懂 慢慢看吧
•   书写得不错，涉及了重要的计算几何的概念。而且讲解细致，深入浅出。由具体事例引出，抽象概括出一般结论。最后还给出了参考注解，为更深入的理解提供了便利。
•   我平时总是很懒得去写评论，但看了这本书之后真的觉得有必要来写一写，希望真的需要这本书的朋友可以及时地找到它。每一个章节都以一个很实用的例子作为引子，都有很详实的解决方案，而且是由浅入深，层层递进。最让我觉得感动得是全书370页的正文，引文数达到了330个，即使没有解决的问题也会给我们指出去什么地方可以找答案。我也非常感谢看过这本书的朋友给出的建议，让我找到了这本书
•   对NOI很有帮助，建议先看高级数据结构，再看此书。
•   从事计算机图形处理人员必备的参考书，尤其是做研究的．
•   内容全面具体
•   很不错的一本书，讲的很详细
•   相当好的一本书，翻译质量也不错，就是需要一定的逻辑能力哦，哈哈，向困难出发。。。
•   易懂 适合入门
•   印刷很好，还没有看完。
•   但是很喜欢
•   不错，有点难
•   的确是一本难得的好书~~
•   相当好,受益颇多
•   非常好的书。。。支持。
•   树种介绍了各种算法以及应用，但却是还是需要一定的数学基础，开卷有益吧
•   书写的比较欧美风格，不过表述不是很容易理解，而且有时候可能是没法理解。译者很多时候都得加上“译者注”。内容介绍的比较多，而且比较全面。唯一的缺陷就是，在当当上买了书，结果少页重页了，换了后还是那个毛病。
•   读这本书让我受益匪浅！盼望已久的好书！
•   书不错，速度很慢！
•   送书的速度和质量都挺好的
•   不可多得好书，写的很简单明了，推荐数学系的做软件开发看看~
•   感觉理论性有点强，不过周培德的那本好
•   　　怎么做Delauny三角剖分？里面步骤非常清晰和理。好像是一个老师手把手地教。而且这章用的不是旧的1985年divide-conquer方法，而是新的1992年的randomized incremental方法.
•   　　这本书是给研究生级别的学生读的. 这书不知为什么比较难懂. 可能是我自己的问题. 我认识的数学系的人感觉这书读起来很怪, 计算机系的也感觉有点难理解. 如果发现读的有压力, 推荐也可以看看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(只有log(n)的加速...真蛋痛, 不过可以用来improve theoretical bounds).
  　　学到了如何O(n)的空间, O(log(n))做point location. 这个的让我orz的内容.
  　　
  　　这两部分真的很有用, 有时发现很多问题都能转换成为point location或者range query.
  　　
  　　曾经看过点projective geometry, 应该是比较熟悉duality的... 但是看到这本书里面的duality, 才发现这有多么的有用. Mitchell告诉我们, 在发现duality之前, 1个问题都会弄出两个paper出来, 一个是paper, 一个是dual paper. 哈哈哈哈哈(真冷...)
  　　
  　　Art gallery theory的证明, 竟然用了graph theory. 实际上CG里面还有不少其他可以用到graph theory的东西. 这是我感觉很有意思的部分.
  　　
  　　习题真的非常精彩啊. 我想分享我曾今做的一个题. 由于我是和作业一起做的, 所以以下这题可能并不存在于书上.
  　　
  　　给蓝色和红色的点n个. 是否存在一个圆, 使得所有的蓝点在圆的内部, 所有的红点在圆的外部呢?
  　　
  　　我当时想了很久, 似乎弄出了超级复杂的O(n log n)的用到Delaunay triangulation的算法...现在记不得了... 我和一个我喜欢的女生说过"你做出这题一定要给我打个电话哦." 我现在还在等待...
  　　
  　　实际上有一个O(n)的算法.
  　　
  　　还有一题, 是我做TA的时候, 交给本科生做的.
  　　
  　　假如art gallery里面的guard可以看到反射k次的光, (光的反射就是入射角=反射角. 如果射到一个vertex, 光就被吸收). Art gallery theorem会怎么改变呢? (刚开始看答案似乎满难, 后来发现蛮简单的)
  　　
  　　Open Problem:
  　　如果可以看到反射无限次的光, art gallery theorem又会有什么改变呢?
•   　　这本书是我导师推荐的，作本科毕业设计的课题就是做range search tree的data structure。后来读了其他部分，也很有意思。由浅入深的一些算法。书不厚，读起来没有压力
•   　　因为上课， 这本书当时也算仔仔细细看了大半了。
  　　
  　　如果现在让我来回忆 这本书讲了什么？ 我能记得的只有几个算法思想： amortized algorithm， sweeping line， randomly increamenting, divide and conquer, 以及想让人破脑袋的无数习题。
  　　
  　　一些复杂的数据结构， 例如voronoi diagram的建立或者是判断line segment intersection都要用sweeping line algorithm及其变种， 所有点都看作event， sweeping动态维持一个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个小问题， 然后加起来发现时间复杂度还相当低。
  　　
  　　此外， 这本书上还有一大堆空间数据结构， 比如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里有讲。