计算几何及应用

第一章 引论

1.1 几何基础知识

1.1.1 基本概念

1.1.2 几何对偶

1.2 算法的复杂度

1.2.1 算法复杂度的度量方法

1.2.2 排序时间复杂度的下界

1.3 数据结构

习题

参考文献

第二章 二维凸包

2.1 凸包的定义

2.2 极端点和极端边

2.3 礼品包裹算法

2.4 凸包的快速算法

2.5 Graham算法

2.5.1 基于堆栈的初步算法

2.5.2 算法实现细节的讨论

2.5.3 改进的Graham算法

2.6 下限

2.7 增量算法

2.8 分而治之算法

2.8.1 算法描述

2.8.2 算法分析

习题

参考文献

第三章 凸包扩展

3.1 多面体

3.1.1 引言

3.1.2 正则多面体

3.1.3 多面体的欧拉公式

3.2 三维凸包算法

3.2.1 礼品包裹算法

3.2.2 分而治之算法

3.2.3 增量算法

3.3 简单多边形的凸包计算

3.3.1 计算简单多边形凸包的局部凸算法

3.3.2 简单多边形凸包计算的“陷阱”算法

3.3.3 简单多边形凸包的Melkman算法

3.4 凸包的近似算法

3.4.1 凸包的近似算法

3.4.2 二维凸包近似算法精度的讨论及其在三维扩展

3.4.3 近似凸包算法的应用

3.5 点集的Maxima

3.6 a-shapes

3.7 点集的相关几何图结构

习题

参考文献

第四章 Voronoi图

4.1 基本概念

4.2 半平面

4.3 Voronoi图的基本性质

4.4 Voronoi图的构造方法

4.4.1 增量法

4.4.2 分而治之法

4.4.3 扫描线法

习题

参考文献

第五章 广义Voronoi图

5.1 加权Voronoi图

5.1.1 能量图

5.1.2 加法加权Voronoi图

5.1.3 乘法加权Voronoi图

5.1.4 圆与球的Voronoi图

5.2 高阶Voronoi图

5.2.1 基本概念

5.2.2 基本性质

5.3 最远点Voronoi图

5.3.1 基本概念

5.3.2 基本性质

第六章 点集的Delaunay三角剖分

第七章 多边形剖分

第八章 几何搜索

第九章 相交计算

第十一章 可见多边形与可见图

第十二章 机器人运动规划

第十三章 随机算法第十章 排列

第十四章 并行计算几何

第十五章 计算几何研究和应用举例

《计算几何及应用》比较全面地介绍了计算几何的基本问题、基础理论和算法。《计算几何及应用》前12章分别介绍了凸包、Voronoi图、三角剖分、多边形剖分、几何搜索、相交计算、排列、可见性计算、路径规划等基本计算几何问题和算法，第13、14章则分别探讨了若干随机和并行的计算几何算法，最后一章给出了关于计算几何的几个实际研究和应用中的例子。《计算几何及应用》在注重介绍计算几何基础理论的同时，也注意介绍简洁、实用和易编程的算法，力求易读、易懂，并使读者能够应用这些理论和算法。为便于消化和理解书中内容，每章末附有习题，以及大量参考文献。

《计算几何及应用》可作为高等院校计算机及应用数学等学科的本科生、研究生学习计算几何的教材，也可作为从事计算几何研究或应用的其他科技工作者的参考用书。