计算几何：算法设计与分析（第2版）——中国计算机学会学术著作丛书 (2008 年度畅销榜NO.1365 )

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

第2版 前言\r\n第1版 前言\r\n第0章 预备知识\r\n 0.1 算法与数据结构\r\n 0.1.1 算法\r\n 0.1.2 数据结构\r\n 0.2 相关的几何知识\r\n 0.2.1 基本定义\r\n 0.2.2 线性变换群下的不变量\r\n 0.2.3 几何对偶性\r\n 0.3 计算模型\r\n第1章 几何查找(检索)\r\n 1.1 点定位问题\r\n 1.1.1 点q是否在多边形P内\r\n 1.1.2 确定点q在平面剖分中的位置\r\n 1.1.3 Z1-3算法\r\n 1.2 范围查找问题\r\n 1.2.1 多维二叉树(k-D树)的方法\r\n 1.2.2 直接存取方法\r\n 1.2.3 范围树方法\r\n 1.3 判定点集是否在多边形内\r\n 1.4 平面网络的处理与点q的定位\r\n第2章 多边形\r\n 2.1 凸多边形\r\n 2.2 简单多边形\r\n 2.3 多边形的三角剖分\r\n 2.4 多边形的凸划分\r\n 2.5 连接不相交线段成简单多边形(链)\r\n 2.6 下料问题\r\n 2.7 红外图像边缘提取\r\n 2.8 满足特定条件的多边形划分\r\n 2.9 多边形与多边形链\r\n 2.10 圆弧、直线段组成的多边形顶点凸、凹性的确定\r\n 2.11 多边形放大、缩小及移动\r\n 2.12 带状多边形的处理\r\n第3章 凸壳及其应用\r\n 3.1 凸壳的基本概念\r\n 3.2 计算平面点集凸壳的算法\r\n 3.2.1 卷包裹法\r\n 3.2.2 格雷厄姆方法\r\n 3.2.3 分治算法\r\n 3.2.4 Z3-1算法与Z3-2算法\r\n 3.2.5 实时凸壳算法\r\n 3.2.6 增量算法\r\n 3.2.7 近似凸壳算法\r\n 3.3 计算平面多边形顶点凸壳的算法\r\n 3.4 计算平面多边形链顶点凸壳的算法\r\n 3.4.1 概念、算法思想与描述\r\n 3.4.2 解释与时间复杂性\r\n 3.5 计算平面线段集凸壳的算法\r\n 3.6 计算三维空间点集凸壳的算法\r\n 3.6.1 基本概念\r\n 3.6.2 卷包裹法\r\n 3.6.3 分治算法\r\n 3.6.4 Z3-8算法\r\n 3.6.5 增量算法\r\n 3.7 凸壳的应用\r\n 3.7.1 确定任意多边形的凸、凹顶点\r\n 3.7.2 利用凸壳求解货郎担问题\r\n 3.7.3 凸多边形直径\r\n 3.7.4 连接两个多边形成一条回路\r\n第4章 Voronoi图、三角剖分及其应用\r\n第5章 交与并及其应用\r\n第6章 矩形几何\r\n第7章 几何体的排列\r\n第8章 算法的运动规划\r\n第9章 几何拓扑网络设计\r\n第10章 随机几何算法与并行几何算法\r\n待解决的问题\r\n算法索引\r\n参考文献

第一台电子计算机诞生于20世纪40年代. 到目前为止, 计算机的发展已远远超出了其创始者的想象. 计算机的处理能力越来越强, 应用面越来越广, 应用领域也从单纯的科学计算渗透到社会生活的方方面面： 从工业. 国防. 医疗. 教育. 娱乐直至人们的日常生活, 计算机的影响可谓无处不在. 计算机之所以能取得上述地位并成为全球最具活力的产业, 原因在于其高速的计算能力. 庞大的存储能力以及友好灵活的用户界面. 而这些新技术及其应用有赖研究人员多年不懈的努力. 学术研究是应用研究的基础, 也是技术发展的动力. 自1992年起, 清华大学出版社与广西科学技术出版社为促进我国计算机科学技术与产业的发展, 推动计算机科技著作的出版, 设立了“计算机学术著作出版基金”, 并将资助出版的著作列为中国计算机学会的学术著作丛书. 时至今日, 本套丛书已出版学术专著近50种, 产生了很好的社会影响, 有的专著具有很高的学术水平, 有的则奠定了一类学术研究的基础. 中国计算机学会一直将学术著作的出版作为学会的一项主要工作. 本届理事会将秉承这一传统, 继续大力支持本套丛书的出版, 鼓励科技工作者写出更多的优秀学术著作, 多出好书, 多出精品, 为提高我国的知识创新和技术创新能力, 促进计算机科学技术的发展和进步做出更大的贡献. 中国计算机学会 2002年6月14日

周培德，1941年生，湖北省武穴市人，1965年毕业于武汉大学数学系，任北京理工大学计算机系教授。2001年9月退休。主要论著有《计算几何——算法分析与设计》、《算法设计与分析》、《计算中的基本理论与方法》，代表性论文有《求解k一中心问题的快速算法》、《平面散乱点线集三角剖分的算法》、《平面线段集三角剖分的算法》、《连接不相交线段成简单多边形的算法》、《确定任意多边形凸凹顶点的算法》、《货郎担问题的几何解法》、《分割多边形成凸多边形算法》等。

第2版前言 第2版对第1版的补充与修改如下：新增26节(1. 1. 3, 1. 4, 2. 5, 2. 6, 2. 7, 2. 8, 2. 9, 2. 10, 2. 11, 2. 12, 3. 3, 3. 4, 3. 5, 4. 4, 4. 5, 4. 6. 9, 4. 6. 11, 4. 6. 12, 4. 6. 13, 5. 6, 8. 1. 2, 8. 1. 3, 8. 1. 4, 8. 7, 9. 1. 3, 9. 1. 4), 删去3节, 修改10节. 新增的内容都是作者最近三年内的研究成果(49个算法, 使作者设计的Z算法增至88个, 占全书算法总数62％). 这里需要再次强调, 为了给读者留下一定的思考余地, 书中新增加的某些Z算法仍然是以基本形式出现的. 作者才疏学浅, 新增内容错误在所难免, 敬请同行与读者批评指正. 周培德 2004年9月 Email：zhou_pd@sina. com http：／／www. china biz 114. com／zhoupd. htm 第1版前言 1975年, Shamos(沙莫斯)和Hoey(霍伊)利用计算机有效地计算平面点集的Voronoi图, 并发表了一篇著名论文, 从此计算几何诞生了. 自那时以来该研究领域取得了辉煌的成果, 使得计算几何成为理论计算机科学领域中一个新的极有生命力的子领域, 并且, 计算几何中的研究成果已在计算机图形学. 化学. 统计分析. 模式识别. 地理数据库以及其他许多领域中得到了广泛的应用. 计算几何研究的典型问题由几何基元(geometric primitives). 查找. 优化等问题类组成. 首先, 几何基元包括凸壳和Voronoi图. 多边形的三角剖分. 划分问题(partition problems)与相交问题. Ed+1中点集S的下凸壳在Ed中的投影恰好是点集S在Ed中投影点的Delaunoy三角剖分, 然后由Delounay三角剖分可以容易地得到Voronoi图. 换言之, Voronoi图是凸壳的特例, 因此构造Ed+1中点集凸壳的算法也可以用于构造Ed中点集的Voronoi图. 对多边形的三角剖分问题可以提出如下要求：设计复杂度低的算法构造多边形三角剖分以及设计三角形最小角最大化的三角剖分算法, 分割线段长度之和最小的三角剖分算法. 前者已有线性时间的算法. 划分问题是多边形三角剖分的推广, 它要求把几何体划分成若干好的部分. 所谓好的部分通常是指下述两个目标之一：划分成尽量少的凸部分, 各凸部分最小角最大化. 另外, 在几何体中可以加入Steiner点(新的顶点), 然后再进行划分, 使得划分线段长度之和最小化或者提出其他要求. 二维中的典型相交问题是：给定平面上n条直线段, 确定所有的相交线对. 三维中的相交问题一般考虑两个凸多面体的交以及两个多面体的交. 其次, 几何查找包括点定位. 可视化. 区域查找等问题. 计算机图形学. 数据库中的区域查找及地理图形中的点定位等都是几何查找中的典型例子. 在平面细分(planar subdivision)中定位一个询问点或者在Ed(d≥3)内由72个超平面构成的结构中定位询问点的问题是一个典型问题, 现在不仅有解决这个问题的确定型算法, 而且设计了动态随机增量算法. 给定平面上n个顶点的简单多边形P, 由点q向任一方向引射线l, 确定l与P相交的第一条边, 这个问题的解决为可视化问题的求解提供了前提. Ed中给定点集S及区域集合B, b∈B, 要求在b中查找S中的点, 这是区域查找问题. 再次, 几何优化包括参数查找和线性规划. 参数查找技术是将一个优化问题的检验算法变成寻找解的算法, 它必须满足某些条件(检验算法是可以并行的), 并且具有广泛的应用性. 例如, 可用它来求解平面中2-中心问题, 还可以用来完成三维空间中射线的安置. 众所周知, 有确定变元数目的线性规划问题已有线性时间算法求解, 但对于广义线性规划是否存在多项式时间算法还有待进一步研究. 此外, 计算几何中各种问题的下界的确定. 推导下界的方法以及求解各种几何问题的算法的复杂性分析等, 也是计算几何研究的重要内容. 计算几何中引入随机化之后, 已经设计出非常有效的概率算法求解诸多几何问题. 随机化给几何算法设计带来两种新的设计思想：基于随机抽样的分治方法, 利用随机顺序插入产生随机增量结构. 此外, 随机几何算法的复杂性分析以及随机增量结构的非随机化也是重要的研究内容. 计算几何的新近发展包括几何抽样理论. 计算实代数几何. 计算拓扑. 运动规划. 并行计算几何. 隐藏面的移动. 结构和图形. 网络生成以及计算机视觉中的几何问题等. 计算机在各学科领域深层次的应用将为计算几何提出更多的研究问题, 反之, 计算几何的研究成果也将促进这些学科的进一步发展. 本书是以上述部分问题的前人研究成果与作者在本领域中所做的工作为基础撰写而成的. 书中主要叙述解决某些几何问题的算法并兼顾复杂性分析. 书中较详细地陈述了98个算法, 其中39个算法是作者提出的, 并编号为Z1-1算法至Z10-2算法. 书中的某些Z算法是以基本形式出现的, 对这些算法可以进行修改并降低复杂性的阶或扩充应用范围, 而且实现这些算法的某些步骤需要一些技巧. 全书共分11章. 第0章是预备知识. 第1章介绍几何查找, 包括点和点集的定位. 范围查找与平面网络的处理. 第2章叙述多边形与多边形的划分及相关问题. 第3. 4. 7章分别介绍计算几何中的三个基本结构：凸壳. Voronoi图与几何体的排列. 第5章阐述线段. 多边形. 半平面. 凸多面体的交, 多边形的并及应用. 第6章介绍矩形几何. 第8章叙述算法的运动规划, 所讨论的问题源于机器人学. 第9章的中心论题是几何拓扑网络设计, 其内容具有广泛的实用性. 第?o章介绍随机几何算法和并行几何算法. 描述算法有诸多形式. 为了便于理解算法又不至于产生二义性, 而且利于编制上机程序, 本书描述算法就不拘泥于某一种形式, 但以步骤. 拟ALGOL语言. 中文语句. 数学表达式及逻辑运算符等相结合的描述形式为主. 另外, 本书以处于一般位置的几何体为讨论对象. 对于退化情况, 则另行处理. 设计求解几何问题(或能转化为几何问题的问题)的算法应具备两个条件, 一是分析并理解问题的几何特征, 二是掌握计算几何中的几何结构. 特殊的算法设计方法及相应的数据结构. 计算几何和计算机科学中的算法设计与分析. 数据结构等学科关系密切, 它常常要用到这些学科的知识. 但由于篇幅有限, 本书将重点阐述计算几何学科的思想方法. 几何结构. 几何问题以及求解这些问题的算法和复杂性分析, 而对算法分析. 数据结构中的相关知识只简略地回忆. 因此, 阅读本书的读者应具备算法设计与分析. 数据结构. 程序设计等领域的知识, 并能熟练地掌握某种高级语言, 比如C语言, 以便上机实现书中描述的算法. 本书可作为计算几何. 计算理论. 计算机图形学. 计算机辅助设计. 机器人学及相关领域科技工作者的参考书, 也可作为计算机科学有关专业研究生或本科高年级学生的教材使用. 本书在撰写中引用了Preparata F P和Shomos M I, O’Rourke J, Mulmuley K, MocGregor Smith J, Mehlhorn K, Chozelle B, Goodrich M T等诸多专家. 学者的文献, 特别是余荣老师提供了大量参考资料, 为缩短本书的撰写周期付出了辛勤的劳动, 作者在此表示衷心的感谢. 此外, 还要感谢清华大学出版社和广西科学技术出版社的“计算机学术著作出版基金”所给予的资助. 由于作者水平有限, 书中定有缺点和错误, 恳请广大读者批评指正. 周培德 1999年12月 于北京理工大学计算机系

无封面