关闭

关闭

封号提示

内容

首页 计算几何-算法与应用(第2版)(中文版).pdf

计算几何-算法与应用(第2版)(中文版).pdf

计算几何-算法与应用(第2版)(中文版).pdf

上传者: tiger 2014-04-10 评分 4.5 0 59 8 267 暂无简介 简介 举报

简介:本文档为《计算几何-算法与应用(第2版)(中文版)pdf》,可适用于高等教育领域,主题内容包含计算几何算法与应用MarkdeBergOtfriedCheongMarcvanKreveldMarkOvermars著邓俊辉译清华大学出版社目录iv符等。

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

类似资料

该用户的其他资料

四元数在刚体定位问题中的应用.pdf

同济大学高等数学第六版.pdf

线性代数 (清华 居余马).pdf

线性代数教材(同济第五版).pdf

线性代数与空间解析几何--黄廷祝 2008.pdf

职业精品

精彩专题

上传我的资料

精选资料

热门资料排行换一换

  • 【Routledge 语言哲学】…

  • 素描.PDF

  • 《表现主义论争》.pdf

  • (美)斯威齐 (美)马格多夫着 …

  • 《明代山人文学研究》张德建着湖南…

  • 时氏内经学(时逸人).pdf

  • 赵冈:中国历史上生态环境之变迁.…

  • 《词心笺评》邵祖平着复旦大学出版…

  • 《白雨斋词话》(清)陈廷焯着上海…

  • 资料评价:

    / 0
    所需积分:0 立即下载

    意见
    反馈

    返回
    顶部