世界著名计算机教材精选·计算几何：算法与应用（第3版）

图书标准信息

• 作者 [德]伯格（Berg M.D.） 著；邓俊辉 译
• 出版社 清华大学出版社
• 出版时间 2009-08
• 版次 1
• ISBN 9787302199380
• 定价 49.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 407页
• 字数 636千字
• 正文语种 简体中文

【内容简介】

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

【目录】

前言
1计算几何：导言
1．1凸包的例子
1．2退化及鲁棒性
1．3应用领域
1．3．1计算机图形学
1．3．2机器人学
1．3．3地理信息系统
1．3．4CAD／CAM
1．3．5其他应用领域
1．4注释及评论
习题

2线段求交：专题图叠合
2．1线段求交
2．2双向链接边表
2．3计算子区域划分的叠合
2．4布尔运算
2．5注释及评论
习题

3多边形三角剖分：画廊看守
3．1看守与三角剖分
3．2多边形的单调块划分
3．3单调多边形的三角剖分
3．4注释及评论
习题

4线性规划：铸模制造
4．1铸造中的几何
4．2半平面求交
4．3递增式线性规划
4．4随机线性规划
4．5无界线性规划问题
4．6*高维空间中的线性规划
4．7*最小包围圆
4．8注释及评论
习题

5正交区域查找：数据库查询
5．1一维区域查找
5．2kd-树
5．3区域树
5．4高维区域树
5．5一般性点集
5．6*分散层叠
5．7注释及评论
习题

6点定位：找到自己的位置
6．1点定位及梯形图
6．2随机增量式算法
6．3退化情况的处理
6．4*尾分析
6．5注释及评论
习题

7Voronoi图：邮局问题
7．1定义及基本性质
7．2构造Voronoi图
7．3线段集Voronoi图
7．4最远点Voronoi图
7．5注释及评论
习题

8排列与对偶：光线跟踪超采样
8．1差异值的计算
8．2对偶变换
8．3直线的排列
8．4层阶与偏差
8．5注释及评论
习题

9Delaunay三角剖分：高度插值
9．1平面点集的三角剖分
9．2Delatmay三角剖分
9．3构造Delaunay三角剖分
9．4分析
9．5*随机算法框架
9．5．1半平面求交
9．5．2梯形图
9．5．3Delaunay三角剖分
9．6注释及评论
习题

10更多几何数据结构：截窗
10．1区间树
10．2优先查找树
10．3线段树
10．4注释及评论
习题

11凸包：混合物
11．1三维凸包的复杂度
11．2构造三维凸包
11．3分析
11．4*凸包与半空间求交
11．5再论Voronoi图
11．6注释及评论
习题

12空间二分：画家算法
12．1BSP树的定义
12．2BSP树及画家算法
12．3构造BSP树
12．4*三维BSP树的规模
12．5低密度场景的BSP树
12．6注释及评论
习题

13机器人运动规划：随意所之
13．1工作空间与C-空间
13．2点机器人
13．3Minkowski和
13．4平移式运动规划
13．5允许旋转的运动规划
13．6注释及评论
习题

14四叉树：非均匀网格生成
14．1均匀及非均匀网格
14．2点集的四叉树
14．3从四叉树到网格
14．4注释及评论
习题

15可见性图：求最短路径
15．1点机器人的最短路径
15．2构造可见性图
15．3平移运动多边形机器人的最短路径
15．4注释及评论
习题

16单纯形区域查找：再论截窗
16．1划分树
16．2多层划分树
16．3切分树
16．4注释及评论
习题
参考文献
图表索引
观察结论．引理．定理及推论索引
关键词索引