计算几何：算法与应用

　　计算几何是计算机理论科学的一个重要分支。自20世纪70年代末从算法设计与分析中独立出来起，不到30年，该学科已经有了巨大的发展，不仅产生了一系列重要的理论成果，也在众多实际领域中得到了广泛的应用。本书的前4章对几何算法进行了讨论，包括几何求交、三角剖分、线性规划等，其中涉及的随机算法也是本书的一个鲜明特点。第5章至第10章介绍了多种几何结构，包括几何查找、kd树、区域树、梯形图、Voronoi图、排列、Delaunay三角剖分、区间树、优先查找树以及线段树等。第11章至第16章结合实际问题，继续讨论了若干几何算法及其数据结构，包括高维凸包、空间二分及BSP树、运动规划、网格生成及四叉树、最短路径查找及可见性图、单纯性区域查找及划分树和切分树等，这些也是对前十章内容的进一步深化。本书不仅内容全面，而且紧扣实际应用，重点突出，既有深入的讲解，同时每章都设有“注释及评论”和“习题”，为读者更深入的理解提供了可能。因此近年来作为教材一直流行于世界众多大学校园中。我国在计算几何方面的研究起步较晚，相信本书的出版能对国内此方面教学工作的开展有所推动。本书前言前言20世纪70年代末，计算几何从算法设计与分析中孕育而生.今天，它不仅拥有自己的学术刊物和学术会议，而且形成了一个由众多活跃的研究人员组成的学术群体，因此已经成长为一个被广泛认同的学科.该领域作为一个研究学科之所以会取得成功，一方面是由于其涉及的问题及其解答本身所具有的美感，另一方面，也是由于在众多的应用领域（诸如计算机图形学、地理信息系统和机器人学等）中，几何算法都发挥了重要的作用.解决许多几何问题的早期算法，要么速度很慢，要么难以理解与实现.随着近年来一些新的算法技术的发展，此前的很多方法都得到了改进与简化.在这本教材中，我们力图使这些现代的算法能够被更广泛的读者理解和接受.本书既是面向计算几何课程的一本教材，同时也可用于自学.本书的结构.除“导言”外，每一章都从来自应用领域的某一实际问题入手，这个问题将被转化为一个纯粹的几何问题，并通过计算几何所提供的方法得到解决.每一章所讨论的，实质上就是对应的几何问题，以及解决该问题所需要的概念与方法.我们根据所希望覆盖的计算几何专题，来选取有关的应用；而就具体的应用领域而言，这些介绍还远远不够全面.引入这些应用的目的，只是为了激发读者的兴趣；而各章本身的目的，并不在于为这些问题提供现成可用的解决方法.虽然如此，我们还是认为，为了有效地解决应用中的几何问题，计算几何方面的知识是非常重要的.我们希望本书不仅能够吸引从事算法研究的学者，而且对应用领域的读者也同样有所帮助.同一几何问题，可能有多种不同的解决方法，不过，在论述大多数几何问题时，我们将只给出其中一种.我们通常所选取的，都是最易于理解与实现的方法.我们也十分注意，尽力使本书能够涵盖更多的方法，比如分治策略、平面扫描以及随机算法等.对每个问题可能的种种变型，我们也不打算面面俱到；我们觉得，更重要的是首先对计算几何中的各个主要问题作一介绍，而不是过于深入地去探究少数专题的细枝末节.某些章的若干节标有星号.这些节的内容涉及解法的改进与扩展，或者解释了不同问题之间的相互关联.就对后续章节的理解而言，它们并不十分重要.每一章的最后，都由名为“注释及评论”的一节进行概括总结.这些节会给出对应各章所介绍结果的来龙去脉，概述其他的解决方法、一般化处理方法及改进，并给出参考文献.虽然这些节可以跳过去，但是对于那些希望就某一章的专题作进一步了解的读者来说，其中的材料都是非常有用的.每一章的后面，都附有一定数量的习题.其中有些题目旨在检查读者对内容的理解程度，也有些题目是对书中内容的推广，需要精心解答.高难度的问题以及对应于标有星号各节的问题，也被标上星号.课程大纲.尽管在很大程度上，本书各章之间是相互独立的，但是在进行介绍时，最好还是不要随意打乱其次序.例如，第2章介绍了平面扫描算法，故在阅读采用了这一方法的其他各章之前，最好首先了解该章的内容.出于同样的考虑，在进入有关随机算法的各章之前，也应该首先阅读第4章.如果是作为计算几何的第一门课程，我们建议教师按照书中的次序来讲授前10章.根据我们的经验，这10章覆盖了任何一门计算几何课程都必须介绍的概念和方法.如果还有可能顾及更多的内容，可以在后面6章中进行挑选.先修要求.作为教材，本书既适用于高年级本科生的课程，也适用于低年级研究生的课程，具体安排视课程的其他要求而定.读者应该具备算法设计与分析、数据结构的基本知识：他们必须熟知大O记号，以及诸如排序、二分查找和平衡查找树等基本的算法技术.读者不需要对这里所涉及的应用领域有所了解，也几乎不需要什么几何的知识.在对随机算法进行分析时，会用到一些非常基本的概率理论.实现.本书中的算法都是以伪代码的形式给出，虽略显概括笼统，但也算详尽，实现起来相对容易.值得一提的是，我们还尝试着介绍了处理退化情况的方法，在具体实现过程中如不能解决好这一问题，往往会使整个计划落空.我们认为，动手实现其中一个或多个算法将十分有益；这可以令你获得对算法复杂度的实际感受.每一章都可以当成一个编程训练的课程项目.根据可利用时间的多少，你既可以只实现算法本身，也可以连同应用系统一起完成.为了实现一个几何算法，若干基本的数据类型（点、直线和多边形等）以及对其实施操作的一些基本例程都是必需的.实现这些基本例程并使之具有稳健性，绝非易事，为此需要投入大量的时间.自己动手这样做一次不无裨益，然而如果能够找到一个提供基本数据类型及其操作例程的现成的软件库，将很有帮助.在我们的万维网页上，可以找到指向这类软件库的链接.万维网站.本书还附有一个万维网站，该网站提供了大量的附加材料，例如本书的勘误补遗、指向几何软件的链接、指向一个包含近1万篇计算几何论文的在线文献库的链接，以及指向提供有关计算几何信息的其他一些网站的链接.我们的地址是：http：//www.cs.uu.nl/geobook/如果您发现了书中的错误，或是对本书有什么建议，也可以通过该页面与我们联系.关于第2版.第2版与第1版在大部分内容上都是相同的；不同之处主要在于针对一些缺陷进行了修正.原则上，选课的学生依然可以使用第1版.不过那样的话，应该注意到以下的变动：首先，我们对所有的习题作了仔细的检查，原先的一些习题已被重新表述或者删去，同时增添了一些新的习题.其次，第4章和第7章的改动较大——前者对无界线性规划问题的论述与初版不同，后者有关算法的若干细节也有所改动.致谢.编写教材是一项耗时的工作，即便有四位作者共同合作，也不例外.在过去几年中我们得到了很多人的帮助：关于本书应该包括、不应该包括哪些内容，有些人提供了有益的建议；有些人在阅读初稿后对如何修改提出了建议；另一些人则找出并更正了书中的错误.特别地，我们要感谢PankajAgarwal、HelmutAlt、MarshallBern、JitBose、HazelEverett、GeraldFarin、SteveFortune、GeertJanGiezeman、MordecaiGolin、DanHalperin、RichardKarp、MatthewKatz、KlaraKedem、NelsonMax、RenevanOostrum、HenryShapiro、SvenSkyum、JackSnoeyink、GertVegter、PeterWidmayer、CheeYap和GuntherZiegler.本书的初稿，曾经在我们系和其他系开设的课程中试用.我们要感谢所有的学生，虽然那个版本的不完整性以及其中的错误给他们造成了很大的麻烦，但正是在他们的帮助下，本书才能历经磨砺，善果终成.我们也要感谢SpringerVerlag出版社，在本书最终完成的阶段，它为我们提供了支持.最后，我们还要感谢荷兰科学研究组织（NetherlandsOrganizationforScientificResearch，N.W.O.）

暂缺《计算几何：算法与应用》作者简介

第1章 计算几何：导言
  1.1 凸包的例子
  1.2 退化及稳健性
  1.3 应用领域
  1.4 注释及评论
  1.5 习题
第2章 线段求交：专题图叠合
  2.1 线段求交
  2.2 双向链接边表
  2.3 计算子区域划分的叠合
  2.4 布尔运算
  2.5 注释及评论
  2.6 习题
第3章 多边形三角剖分：画廊看守
  3.1 覆盖与三角剖分
  3.2 多边形的单调块划分
  3.3 单调多边形的三角剖分
  3.4 注释及评论
  3.5 习题
第4章 线性规划：铸模制造
  4.1 铸造中的几何
  4.2 半平面求交
  4.3 递增式线性规划
  4.4 随机线性规划
  4.5 无界线性规划问题
  *4.6 高维空间中的线性规划
  *4.7 最小包围圆
  4.8 注释及评论
  4.9 习题
第5章 正交区域查找：数据库查询
  5.1 一维区域查找
  5.2 kd树
  5.3 区域树
  5.4 高维区域树
  5.5 一般性点集
  *5.6 分散层叠
  5.7 注释及评论
  5.8 习题
第6章 点定位：找到自己的位置
  6.1 点定位及梯形图
  6.2 随机增量式算法
  6.3 退化情况的处理
  *6.4 尾分析
  6.5 注释及评论
  6.6 习题
第7章 Voronoi图：邮局问题
  7.1 定义及基本性质
  7.2 构造Voronoi图
  7.3 注释及评论
  7.4 习题
第8章 排列与对偶：光线跟踪超采样
  8.1 差异值的计算
  8.2 对偶变换
  8.3 直线的排列
  8.4 层阶与偏差
  8.5 注释及评论
  8.6 习题
第9章 Delaunay三角剖分：高度插值
  9.1 平面点集的三角剖分
  9.2 Delaunay三角剖分
  9.3  构造Delaunay三角剖分
  9.4 分析
  *9.5 随机算法框架
  9.6 注释及评论
  9.7 习题
第10章 更多几何数据结构：截窗
  10.1 区间树
  10.2 优先查找树
  10.3 线段树
  10.4 注释及评论
  10.5 习题
第11章 凸包： 混合物
  11.1 三维凸包的复杂度
  11.2 构造三维凸包
  *11. 3分析
  *11.4 凸包与半空间求交
  *11.5 再论Voronoi图
  11.6 注释及评论
  11.7 习题
第12章 空间二分：画家算法
  12.1 BSP树的定义
  12.2 BSP树及画家算法
  12.3 构造BSP树
  *12.4 三维BSP树的规模
  12.5 注释及评论
  12.6 习题
第13章 机器人运动规划：随意所之
  13.1 工作空间与C空间
  13.2 点机器人
  13.3 Minkowski和
  13.4 平移式运动规划
  *13.5 允许旋转的运动规划
  13.6 注释及评论
  13.7 习题
第14章 四叉树：非均匀网格生成
  14.1 均匀及非均匀网格
  14.2 点集的四叉树
  14.3 从四叉树到网格
  14.4 注释及评论
  14.5 习题
第15章 可见性图：求最短路径
  15.1 点机器人的最短路径
  15.2 构造可见性图
  15.3 平移运动多边形机器人的最短路径
  15.4 注释及评论
  15.5 习题
第16章 单纯形区域查找：再论截窗
  16.1 划分树
  16.2 多层划分树
  16.3 切分树
  16.4 注释及评论
  16.5 习题
参考文献
关键词索引