内 容 简 介 本书系统地介绍了计算几何中的基本概念、求解诸多问题的算法及复杂性分析，概括了求解几何问题所特有的许多思想方法、几何结构与数据结构。全书共分10章，包括: 预备知识，几何查找（检索）,多边形,凸壳及其应用,Voronoi图、三角剖分及其应用，交与并及其应用，多边形的获取及相关问题，几何体的划分与等分，路径与回路，几何拓扑网络设计等。 本书可作为高等院校计算机、自动化等专业研究生或本科高年级学生的教材或教学参考书,也可供软件开发人员、相关专业科技工作者参考。

第4版对第3版的补充与修改如下： 1. 增加了作者于2008年1月至2010年2月发明的118个计算机算法。全书303个（其中232个已编码，71个未编码）计算机算法均为作者所发明。 2. 删去第3版中的第10章及所有他人发明的47个计算机算法，这是由于作者难以征得这些算法发明人的同意（避免引起不必要的纠纷），故将此删去。 3. 对4.2.2节等作了必要的修改。 本书是作者长期从事计算几何领域研究所取得的成果的汇总，它不是一部入门的教材。在内容叙述方面（第4版新增部分），力求简要，因此不适合初学者阅读。此外，有一定基础的读者阅读本书，特别是需要使用其中的某些算法时， 应仔细进行研究，可能还需要作些补充与修改。 美国Smith College计算机科学系Joseph ORourke教授于2009年6月1日给作者发来一封电子邮件： “Your list of open problems shows you are talented and creative.”由此可见，作者提出的待解决问题具有重要意义。期盼国内同行能给予适当关注。 虽然平面点集最小权三角剖分问题已经被证明是NP-难的，但由于平面线段集最小权三角剖分问题与平面点线集最小权三角剖分问题等均为平面 点集最小权三角剖分问题的子问题，故后者的问题性质有待证明。也就是说，平面线段集及平面点线集最小权三角剖分问题属于P类还是NP-难？事实上，这是两个新的悬而未决的问题。 作者提出的待解决问题6，其意义是，如果长时间找不到反例， 那么就增加了对“P=NP”的信念。此外，如果能将货郎担问题输入点 的...