本书系统地介绍了计算机几何中的基本概念、求解诸多问题的算法及复杂性分析，概括了求解几何问题所特有的许多思想方法、几何结构与数据结构。全书共分11章，包括：预备知识、几何查找、多边形、凸壳及其应用、Voronoi图与三角剖分及其应用、交与并及其应用、矩形几何、几何体的排列、算法的运动规划、几何拓扑网络设计、随机几何算法与并行几何算法等。
本书可作为高等院校计算机专业研究生或本科高年级学生的教材，也可作为相关专业科技工作者的参考书。

第0章 预备知识
0.1 算法与数据结构
0.1.1 算法
0.1.2 数据结构
0.2 相关的几何知识
0.2.1 基本定义
0.2.2 线性变换群下的不变量
0.2.3 几何对偶性
0.3 计算模型
第1章 几何查找（检索）
1.1 点定位问题
1.1.1 点q是否在多边形P内
1.1.2 确定点q在平面剖分中的位置
1.1.3 Z1-3算法
1.2 范围查找问题
1.2.1 多维二叉树（k-D树）的方法
1.2.2 直接存取方法
1.2.3 范围树方法
1.3 判定点集是否在多边形内
1.4 平面网络的处理与点q的定位
第2章 多边形
2.1 凸多边形
2.2 简单多边形
2.3 多边形的三角剖分
2.4 多边形的凸划分
2.5 连接不相交线段成简单多边形（链）
2.6 下料问题
2.7 红外图像边缘提取
2.8 满足特定条件的多边形划分
2.9 多边形与多边形链
2.10 圆弧、直线段组成的多边形顶点凸、凹性的确定
2.11 多边形放大、缩小及移动
2.12 带状多边形的处理
第3章 凸壳及其应用
3.1 凸壳的基本概念
3.2 计算平面点集凸壳的算法
3.2.1 卷包裹法
3.2.2 格雷厄姆方法
3.2.3 分治算法
3.2.4 Z1-3算法与 Z3-2算法
3.2.5 实时凸壳算法
3.2.6 增量算法
3.2.7 近似凸壳算法
3.3 计算平面多边形顶点凸壳的算法
3.4 计算平面多边形链顶点凸壳的算法
3.4.1 概念、算法思想与描述
3.4.2 解释与时间复杂性
3.5 计算平面线段集凸壳的算法
3.6 计算三维空间点集凸壳的算法
3.6.1 基本概念
3.6.2 卷包裹法
3.6.3 分治算法
3.6.4 Z3-8算法
3.6.5 增量算法
3.7 凸壳的应用
3.7.1 确定任意多边形的凸、凹顶点
3.7.2 利用凸壳求解货郎担问题
3.7.3 凸多边形直径
3.7.4 连接两个多边形成一条回路
第4章 Voronoi图、三角剖分及其应用
4.1 Voronoi图的基本概念
4.2 构造Voronoi图的算法
4.2.1 半平面的交
4.2.2 增量构造方法
4.2.3 分治法
4.2.4 减量算法
4.2.5 平面扫描算法
4.2.6 构造最远点意义下Voronoi图的算法
4.3 平面点集的三角剖分
4.3.1 平面点集三角剖分的贪心算法
4.3.2 Delaunay三角形剖分与多边形内部点集的三角剖分
4.3.3 平面点集三角剖分的算法
4.4 平面线段集的三角剖分
4.5 平面点线集的三角剖分
4.6 应用
4.6.1 最近邻近
4.6.2 最大化最小角的三角剖分
4.6.3 最大空圆
4.6.4 最小生成树
4.6.5 货郎担问题
4.6.6 中轴
4.6.7 Voronoi图与凸壳的关系
4.6.8 Voronoi图的推广
4.6.9 有约束的Voronoi图
4.6.10 几何数据压缩
4.6.11 车辆定位导航系统的新定位算法
4.6.12 调色
4.6.13 点集增（删）点之后的三角剖分
第5章 交与交及其应用
5.1 线段交的算法
5.2 多边形的交
5.2.1 凸多边形交的算法
5.2.2 星形多边形交的算法
5.2.3 任意简单多边形交的算法
5.3 半平面的交及其应用
5.3.1 半平面的交
5.3.2 两个变量的线性规划
5.4 多边形的并
5.5 凸多面体的交
5.6 应用
5.6.1 地图匹配
5.6.2 地图数据的处理
5.6.3 线段与凸多面体面的交
第6章 矩形几何
6.1 判定垂直、水平线段是否相交的算法
6.2 矩形几何问题的特征解决问题的途径
6.3 矩形并的面积与周长
6.4 矩形关的轮廓
6.5 矩形关的闭包
6.6 矩形关的非平凡轮廓和外轮廓
6.7 矩形的交
6.8 应用举例
第7章 几何体的排列
7.1 基本概念
7.2 确定直线排列的算法
7.3 对偶性
7.4 Voronoi图
7.4.1 一维情况
7.4.2 二维情况
7.5 应用
7.5.1 k-最近邻近
7.5.2 删去隐藏面
7.5.3 特征图
7.5.4 点集的分割
第8章 算法的运动规划
8.1 最短路径
8.1.1 可视图及其构造
8.1.2 Z8-1算法
8.1.3 多面体面上任意两点之间的最短路径
8.1.4 货运汽车调度及行驶路径问题
8.2 移动圆盘
8.3 平移凸多边形
8.4 移动杆状机器人
8.4.1 网格分解
8.4.2 收缩方法
8.5 机器人臂的运动
8.5.1 可达性
8.5.2 构造可达性
8.6 可分离性
8.6.1 多种可分离性
8.6.2 借助于平移的可分离性
8.6.3 分离问题是NP-难的
8.6.4 模拟河内塔问题
8.7 满足一定条件的运动规划
第9章 几何拓扑网络设计
9.1 G（S）问题
9.1.1 最大间隙问题（MAX G）
9.1.2 最小覆盖问题（MIN C）
9.1.3 2-中心问题
9.1.4 k-中心问题
9.1.5 最近对问题（CPP）
9.1.6 所有最近邻近问题（ANNP）
9.1.7 邮局问题（POFP）
9.2 G（E）问题
9.2.1 EMST问题
9.2.2 欧几里得TSP
9.2.3 欧几里得最大生成树问题（EMXT）
9.3 G（S，E）问题
9.3.1 欧几里得Steiner最小树问题（ESMT）
9.3.2 直线Steiner最小树问题（RSMT）
9.4 G问题
9.4.1 有障碍物的最大空隙问题（MAX G）
9.4.2 具有障碍物的欧几里得最短路径问题（ESPO）
9.4.3 具有障碍物的Steiner最小树问题（ESMTO）
第10章 随机几何算法与并行几何算法
10.1 分类和搜索线性表的随机算法
10.1.1 随机二叉树
10.1.2 跳越表
10.2 增量算法
10.2.1 四边形分解
10.2.2 凸多胞形
10.2.3 Voronoi图
10.2.4 构形空间
10.3 动态算法
10.4 随机抽样
10.4.1 具有限界的构形代间
10.4.2 顶-向下的抽样
10.4.3 底-向上的抽样
10.4.4 动态抽样
10.5 并行几何算法
10.5.1 凸壳问题
10.5.2 排列与分解
10.5.3 邻近
10.5.4 几何搜索
10.5.5可视性和最优化
待解决的问题
算法索引
参考文献

周培德：1941年生，湖北省武穴市人。1956年毕业于武汉大学数学系。任北京理工大学计算机系教授。2001年9月退休。长期担任本科生"算法设计与分析"及研究生"计算理论"等课程的教学工作。主要精力集中于计算机算法分析与设计、计算几何等方面的研究。以个人名义在多种学术刊物和全国学术交流会上发表论文60篇，出版学术专著一部、全国统编高等学校教材一部、校"九五"规划研究生教材一部、内部教材八部。主要论著有《计算几何--算法分析与设计》、《算法设计与分析》、《计算中的基本理论与方法》。代表性论文有《求解K-中心问题的快速算法》、《平面散乱点线集三角剖分的算法》、《平面线段集三角剖分的算法》、《连接不相交线段成简单多边形的算法》等。《算法设计与分析》获第三届全国普通高校部级优秀教材一等奖。退休以来，专心从事计算几何及其应用领域的研究工作，为6个课题组，公司设计了20来个算法，在多种期刊上发表学术论文20来篇，提出一批新的问题及解