《计算几何与应用》充分介绍了计算几何的基本问题、基本理论和算法。《计算几何与应用》前12章分别介绍了凸包、Voronoi图、三角分割、多边形分割、几何搜索、交叉计算、排列、可见性计算、路径规划等基本计算几何问题和算法。第13章和14章分别讨论了几种随机和并行的计算几何算法。最后一章给出了计算几何的几个实际研究和应用的例子。《计算几何与应用》在重点介绍计算几何基础理论的同时，还重点介绍了简洁、实用、易编程的算法，力求易读易懂，使读者能够应用这些理论和算法。为了方便消化和理解书中的内容，每章末都附有习题和大量参考文献。《计算几何与应用》可以作为高校计算机和应用数学的本科学生、研究生学习计算几何的教材，也可以作为从事计算几何的其他科技研究或应用的参考。
目录
- 前言
- 第一章 引论
- 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三角剖分
- 第七章 多边形剖分
- 第八章 几何搜索
- 第九章 相交计算
- 第十一章 可见多边形与可见图
- 第十二章 机器人运动规划
- 第十三章 随机算法第十章 排列
- 第十四章 并行计算几何
-
第十五章 计算几何研究和应用举例
