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

前言
1 计算几何：导言
1.1 凸包的例子
1.2 退化及鲁棒性
1.3 应用领域
1.3.1 计算机图形学
1.3.2 机器人学
1.3.3 地理信息系统
1.3.4 CAD／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.2 kd-树
5.3 区域树
5.4 高维区域树
5.5 一般性点集
5.6 分散层叠
5.7 注释及评论
习题
6 点定位：找到自己的位置
6.1 点定位及梯形图
6.2 随机增量式算法
6.3 退化情况的处理
6.4 木尾分析
6.5 注释及评论
习题
7 Voronoi图：邮局问题
7.1 定义及基本性质
7.2 构造Voronoi图
7.3 线段集Voronoi图
7.4 最远点Voronoi图
7.5 注释及评论
习题
8 排列与对偶：光线跟踪超采样
8.1 差异值的计算
8.2 对偶变换
8.3 直线的排列
……
9 Delaunay三角剖分：高度插值
10 更多几何数据结构：截窗
11 凸包：混合物
12 空间二分：画家算法
13 机器人运动规划：随意所之
14 四叉树：非均匀网格生成
15 可见性图：求最短路径
16 单纯形区域查找：再论截窗
参考文献
图表索引
观察结论、引理、定理及推论索引
关键词索引

2 线段求交：专题图叠合
对于身处异国他乡的游客而言，再没有什么要比地图更具价值的信息来源了。地图可以告诉你，游客们对哪些地方最感兴趣；它们也会告诉你，要沿着哪些公路与铁路，才能到达这些名胜景点；它们还能指示出小湖泊的位置，等等。不幸的是，有时地图也会令你失望，因为经常会很难找到你所需的信息：纵然你知道某个小镇的大致方位，也可能很难在地图上确定它的具体位置。为了增加地图的可读性，地理信息系统将（不同类型的）信息划分为若干层（layer）。每一层都是一幅专题图（thematic map）——也就是说，存放某一特定类型的信息。这样，某一层可能负责存储有关公路的信息，第二层存放的可能是所有城市的信息，而另一层则存放河流的信息，诸如此类。某些层对应的主题（theme）有可能非常抽象。例如，可能会有某一层对应于人口密度的分布、平均降雨量、大灰雄的栖息地（如图2.1所示）或者植被的分布。
各层所记录的地理信息，在数据类型上可能差别极大：对应于道路图的那层，可能会将道路存储为一组线段（或者，也可能是曲线）；对应于城市的那一层，可能由一系列的点组成，每个点分别标有某个城市的名称；而在对应于植被分布的那层中，存放的 可能是地图的一个子区域划分（subdivision），其中的每个子区域分别标有对应的植被类型。
……