计算几何算法与应用(第三版)

《计算几何:算法与应用(第3版)》的前4章对几何算法进行了讨论，包括几何求交、三角剖分、线性规划等，其中涉及的随机算法也是《计算几何:算法与应用(第3版)》的一个鲜明特点。第5章至第10章介绍了多种几何结构，包括几何查找、kd树、区域树、梯形图、Voronoi图、排列、Delaunay三角剖分、区间树、优先查找树以及线段树等。第11章至第16章结合实际问题，继续讨论了若干几何算法及其数据结构，包括高维凸包、空间二分及BSP树、运动规划、网格生成及四叉树、最短路径查找及可见性图、单纯性区域查找及划分树和切分树等，这些也是对前10章内容的进一步深化。《计算几何:算法与应用(第3版)》不仅内容全面，目录双向链接边表计算子区域划分的叠合布尔运算汴释及评论习题3多边形三角剖分:画廊看守看守与三角剖分多边形的单调块划分单调多边形的三角剖分注释及评论线性规划:铸模制造铸造中的几何半平面求交谤增式线性规划随机线性规划无界线性规划问题高维空间中的线性规划最小包围圆注释及评论习题S止交区域查找:数据库查询维区域查找树区域树高维区域树一般性点集分散层叠注释及评论习题点定位:找到自己的位置点定位及梯形图随机増量式算法退化情况的处理尾分析注释及评论目录图:邮局问题定义及基本性质构造图线段集最远点图注释及评论8排列与对偶:光线跟踪超采样差异值的计算对偶变换直线的排列层阶与偏差注释及评论习题三角剖分:高度插值平面点集的角削分三角剖分构造三角剖分分析随机算法框架注释及评论№0更多儿何数据结构:截窗区间树优先查找树线段树注释及论习题們1凸包:混合物三维凸包的复杂度构造三维凸包分析凸包与半空间求交再论目录注释及评论习题12空间二分:画家算法树的定义树及画家算法构造树三维树的姚模低密度场景的树注释及评论习题侶机器人运动规划:随意所之工作空间与空间点机器人和平移式运动规划允许旋转的运动规划注释及评论习题№四叉树:非均匀网格生成均匀及非均匀网格点集的四叉树从四叉树到网格注释及评论习题可见性图:求最短路径点机器人的最短路径构造可见性图平移运动多边形机器人的最短路径注释及评论习题悠单纯形区域查找:再论截窗划分树多层划分树切分树注释及记论目录习题参考文献图表索引观察结论、引理、定理及推论索引一关健词索引前言前言十世纪七十年代末,计算几何学()从算法设计与分析中孕育而生。今天,它不仪拥有自己的学术刊物和学术会议,而且形成了个由众多活跃的研究人员组成的学术群体,因此已经成长为个被广泛认同的学科。该领域作为个研究学科之所以会取得成功,·方面是由」其涉及的问题及其解答木身所具有的美感,而另一方面,也是由于在(诸如计算机图形学、地理信息系统和机器人学等)众多的应用领域中,儿何算法都发挥了重要的作用。解决许多几何问题的早期算法,要么速度很慢,要么难于理解与实现。随着近年来一些新的算法技术的发展,此前的很多方法都得到了改进与简化。这本教材力图使得这些现代的算法能够为更泛的读者理解和接受。本书既是面向计算几何课程的一本教材,同时也可用于自学。本书的结构。除《导言》外,这章中的每一章都从来自应用领域的某一实际问题入手。这个问题将被转化为一个纯粹的几何问题,进而通过计算几何所提供的方法加以解决。每章所讨论的,实质上就是对应的那个几何问题,以及解决该问题所需要的概念与方法。我们根据所希望覆盖的计算几何专题,来选取有关的应用;而就具体的应用领域而言,这些介绍还远远不够全面。引入这些应用的目的,只是为了激发读者的兴趣;而各章本身的目的,并不在于为这些问题提供现成可用的解决前言方法。虽然如此,我们还是认为,为有效地解决应用中的几何问题,计算几何方面的知识是非常重要的。希望本书不仅能够吸引来自算法学术圈的那些人,而且对来自应用领域的人们亦是如此。同一几何问题,可能有好几种不同的解决方法,不过,在论述大多数几何问题时,我们将只给出其中·种。我们通常所选取的,都是最易于理解与实现的方法。我们也十分注意,尽力使本书能够涵盖更多的方法,比如分治策略、平面扌描以及随机算法()等等。对每个问题可能的种种变型,我们也不打算面面俱到;我们觉得,更重要的是首先对计算几何中的各个主要问题徹一介绍,而不是过」深入地去探究少数专题的细枝木节。某些章的若干节标有星号。这些节的内容涉及解法的改进与扩展,或者解释了不同问题之间的相互关联。就对后续章节的理解而言,它们并不十分重要。每章最后,都由名为“注释及评论”的一节进行概括总结。这些节会给出对应各章所介绍结果的来龙去脉,概述其它的解决方法、一般化处理方法及改进,并给出参考文献。虽然这些节可以被珧过,但是对于那些希望就某一章的专题做进一步了解的读者来说,其中的材料都是非常有用的。每章后面,都附有一定数量的习题。其中一些旨在检查读者对内容的理解程度,也有些是对书中内容的推广,需要精心解答。高难度的问题以及对应于标有星号各节的问题,也被标上星号。课程大纲。尽管在很大程度上,本书各章之间是相互独立的,但在进行介绍时,最好还是不要随意打乱其次序。例如,第章介绍了平面打措算法,故在阅读采用了这一方法的其它各章之前,最好首先了解该章的内谷。出于同样考虑,在进入有关随机算法的各章之前,也应该首先阋读第章。如果是作为计算几何的第门课程,建议(教师)按照书中的次序来讲授前十章。根据我们的经验,这丨章覆盖了任何一门计算儿何课程都必须介绍的概念和方法。如果还有可能顾及更多的内容,可以在后面六章中进行挑选。先修要求。做为教材,本书既适用于高年级本科生课程,也适用于低年级硏究生课程,具体安排视课桯的其它要求而定。者应具备算法设计与分析、数据结构的基本知识:必须熟知大记号,以及诸如排序、二分査找和平衡査找树等基本的算法技术。读者不需要对这里所涉及的应用领域有所了解,也几乎不需要什么几何知识。在对随机算法进行分析时,会用到一些非常基本的概率理论。实现。夲书中的算法都是以伪代码的形式给出,虽略显慨括笼统,但也算详尽,实现起来相对容易。值得一提的是,我们还尝试着介绍了处理退化情况的方法,在具体实现过程中如不能解决好这一问题,往往会使整个计划落空我们认为,动手实现其中个或多个算法将十分有益;这可以令你获得对算法复杂度的实际感受。每·章都可以当成个编程训练的课程项目。根据可利用吋间的多少,你既可以只实现算法本身,也可以连同应用系统起完成为了实现一个几何算法,若干基本的数据类型点、直线和多边形等以及对其实施操作前言的一些基本例程都是必需的。实现这些基本例程并使之具有鲁棒性,绝非易事,为此需要投入大量的时间。自己动手这样做一次不无裨益,然而如果能够找到一个提供基本数据类型及其捰作例程的现成的软件库,将很有帮助。在我们的万维网页面上,可以找到指向这类软件库的链接万维网站。本书还附有个万维网站,该网站提供了本书各个版本的勘误、所有插图、所有算法的伪代码,以及一些其它资源。其地址是:如果您发现了书中的错误,或是对本书有何建议,可以通过该页面与我们联系。关于第三版。第三版的改动主要有两处:第章“图:邮局问题”中,增加了关于线段图、最远点图的讨论;第章“空间二分:画家算法”中,针对低密度场景的树,作为实际输入模型的导论,増加了一节。外,更正了大量瑕疵与错误〔请参阅网站提供的第:版勘误)每章的“注释及评论”一节也做了更新,以体现新的研究成果及相关文献。为不致影响学生继续在课程学习中沿用第版,第三版尽可能没冇改动原先各节与各习题的编号。致谢。编写教材是项耗吋的⊥作,即便有四位作者共同合作,也不例外。在过去几年中我们得到了很多人的帮助:关于本书应该包括、不应该包括哪些内容,有些人提供了有益的建议,有些人在阅读初稿后对如何修改提岀了建议,另·些人则指出并更止了前两版中的错误。感谢所有这些人,特别要感谢和。感谢出版社给予的建议和支持,使得本书各版本得以出版,并被译成日文、中文及波兰文。最后,还要感谢荷兰科学研究组织(与韩国研究基佥()的人力支持。年月计算几何:导言正漫步于校园的你,突然需要打一个紧急电话。在遍布校园的各个公用电话中,你当然想找到离自己最近的那部。然而,哪一部才是最近的呢?一张校园地图将能帮忙,无论你身处何处,都可以在地图上找到最近的公用电话。这张地图可能会将整个校园划分成不同区域,每个区域都对应着部最近的公用电话(如图所示)。这些区域形状如何?又该如何计算出它们呢?尽管这算不上·个至关重要的问题,它却简要描述了个主要的几何概念,而这概念在众多应用中都扮演着重要的角色。