热门文档
- 2022-09-18 20:22:00 中国人为什么看不起中国人 张鸣
- 2023-04-19 15:04:26 《千家妙方 上册 1982年》(李文亮等编)
- 2023-10-13 17:09:40 楚辞 中华传统诗词经典 可复制-李山-9787101097528
- 2022-09-18 20:22:00 中国兵法之起源 编委会
- 2022-11-24 16:17:09 《性体验与性爱心理》尤里-谢尔巴特赫
- 2022-11-24 16:17:09 《性爱健康指南》石四维编著
- 2023-10-13 17:09:40 超速学习：我这样做，一个月学会素描，一年学会四种语言，完成MIT四年课程-斯科特·扬著，林慈敏译-9789861755533
- 2022-09-18 19:48:57 心理催眠术 迈克尔.赫普,温迪.德雷顿著
- 2023-10-13 17:09:40 初中诗词格律读本 可复制-周建忠 徐乃为 王业强编著-9787101121704
- 2023-10-13 17:09:40 曾国藩家书 中华经典藏书(升级版)可复制-檀作文译注-9787101115482
- 2023-01-11 15:23:39 孔子学院传播研究_刘程 安然著_9787516112922
- 2022-09-18 19:48:57 成功创业72绝招 艾凡著
1、本文档共计 290 页，下载后文档不带www.pdfdz.com水印，支持完整阅读内容。
2、古籍基本都为PDF扫描版，所以文档不支持编辑功能，即不支持文档内文字的复制粘贴。
3、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
4、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
5、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。
2、古籍基本都为PDF扫描版，所以文档不支持编辑功能，即不支持文档内文字的复制粘贴。
3、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
4、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
5、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。
3.2.4Z-1算法和Z2算法643.2.5实时凸壳算法…663.2.6增量算法……703.2.7近似凸壳算法…713.3计算凸壳的算法（三维）…7173763.3.5增量算法…77783.4,2利用凸壳求解货郎担问题…80823.4,4连接两个多边形成一条回路…84第4章V0r0n0i图及其应用…88884.2构造Vor0noi图的算法…92924,2.2增量构造方法…93959742.5平面扫描算法……984.3平面点集的三角剖分…1014.3.1平面点集三角剖分的贪心算法…1014.3.2 Delaunay三角剖分与多边形内部点集的三角剖分…1034.3.3平面点集三角剖分的算法………1054.4 Voronoi图与三角剖分的应用1104,4.2最大化最小角的三角剖分1104.4.5货郎担问题1151164.4.7 Voronoi图与凸壳的关系1214.4.8V0r0n0i图的推广…1234.4.9儿何数据压缩…130第0章预备知识本书叙述的内容不属于欧几里得的几何证明公理化范畴，而是属于欧几里得的几何构造，即由算法和复杂性分析所组成。欧几里得的几何构造满足算法的所有要求：无二义性、有穷性、确定性、能行性、输入、输出、正确性等，在欧几里得的几何构造中，限定了可允许使用的工具（直尺和圆规）及原始运算（圆规的一个脚置于一个给定点或一条直线上：作一个圆：直尺的边通过一个给定点：作一条直线)。但欧几里得原始运算并不能胜任所有的几何计算（比如角的三等分），这一点直到19世纪，阿贝尔、伽罗华等数学家才给出了证明。在一个几何构造过程中，执行原始运算的总次数称为该过程的复杂性度量，这个概念对应于算法的时间复杂度。同样，还有对应于算法的空间复杂度的概念。这是欧几里得几何构造过程复杂性的定量测度。称为计算几何的学科大致有下述几种：Forrest等人依据样条函数处理曲线和曲面(实际上更接近于数值分析)：Minsky和Papert写的一本名为《感知机》的书（副标题为“计算几何”)，该书陈述用简单回路构成的网络实现模式识别的可能性（应属于人工神经网络)：计算机图形学是研究用计算机进行图形信息处理（包括表示、输入、输出、存储、显示、检索与变换等)和图形运算（如图的并、交运算）的一门学科，而不是算法分析：几何定理的机器证明，主要研究定理证明的探索方法及证明过程的推断，而不是几何本身。本书讨论的内容与上述计算几何学科所研究的内容不同，而是属于Shamos的文章(19？5a)中命名的“计算几何”。为了不与上述“计算几何”的命名混淆，并突出Shamos的计算几何是研究几何问题的算法及复杂性的，故本书中将Shamos的计算几何称为S计算几何，而书名仍称为计算几何。欧几里得货郎担问题、最小生成树问题、隐藏线（面）问题和线性规划问题等许多问题是S计算几何研究的基本问题。在19世纪的文献中，已经出现了对这些问题的算法研究，但对几何问题进行几何算法的系统研究还是近20多年的事情。本书将通过对儿何问题的研究，在以下各章节中给出S计算几何的观点、研究方法与几种重要的几何结构。S计算几何的一个基本观点是，经典的几何对象的表征常常不适合于有效算法的设计。因此有必要建立一些概念及相关的性质，以适应于有效算法的设计。本章将介绍有关算法与数据结构的一些知识、几何知识及计算模型。这些内容是以后章节所需要的。0.1算法与数据结构0.1.1算法众所周知，算法是求解一个问题类的无二义性的有穷过程。这里的过程是指求解问题
