一、以凸包为工具求解组合几何题（论文文献综述）
王桂亮[1]（2011）在《基于凸壳的半监督聚类算法研究》文中研究指明半监督聚类算法是目前机器学习和数据挖掘领域的一个研究热点,吸引了众多学者对该领域进行研究,并取得了一定的研究成果。本文对半监督聚类算法进行了研究,提出了一种基于凸壳的半监督聚类算法,并通过实验对其聚类效果进行了验证,一定程度上丰富了半监督聚类算法的研究内容,给半监督聚类问题的求解提供了新的思路,具有一定的科研价值和应用潜力。从机器学习的角度讲,传统的聚类算法属于无监督学习中的一种,而半监督聚类则属于半监督学习。半监督聚类就是利用数据集中带有标签或者限制信息的样本数据辅助聚类的过程,因此,半监督聚类中最重要的问题就是如何有效的利用原始数据中提供的已知标签或限制信息,指导聚类过程,使其趋向于得到较好的结果簇方向。目前存在的半监督聚类算法可以大体分为两大类:基于限制的方法和基于距离的方法。本文提出的SCBCH（基于凸壳的半监督聚类）算法属于后者。从结构上看,本文首先介绍了聚类的相关理论,对聚类中的基本概念进行了解释。由于SCBCH算法属于聚类中的一种,因此,这些概念对SCBCH算法同样适用。同时,还对聚类中的常见簇类型和常用的聚类算法进行了介绍,明确了聚类的通用流程。在随后的内容中,重点讲述了半监督聚类的有关知识,如半监督聚类的研究背景和意义,半监督聚类的基本理论以及发展现状,半监督聚类中的两种常用算法等,为后文中提出SCBCH算法奠定了理论上的基础。第二章中还对聚类质量度量的几种常用方式的原理进行了介绍,为后文中SCBCH算法的有效性验证实验取得的较好效果建立了依据。本文的第三章中对凸壳的相关理论以及常用算法进行了介绍,为本文中提出的SCBCH算法中引入凸壳的缘由进行了理论上的说明。然后,对凸壳构造算法在不同维度数据中的时间复杂度进行了探讨性的实验。结果表明,凸壳算法仅适用于低维空间,同样为SCBCH算法的验证性实验提供了理论支撑。第四章中提出了本文的核心内容SCBCH算法,从算法提出的意义、算法的具体流程、以及算法的验证实验三个方面进行了详细的阐述。验证实验表明,SCBCH这种半监督聚类算法与传统聚类算法相比,对聚类的准确率以及簇间的紧密程度等都有一定程度的提升,符合半监督聚类的特征。与文中介绍的Seeded-KMeans算法（由Sugato Basu提出的一种半监督聚类算法）相比,聚类效果相差不大。因此,可以说明本文提出的算法在一定程度上效果良好。最后对全文进行了总结,并指明了下一步的研究和工作方向,对基于凸壳的半监督聚类算法的进一步发展提出了自己的看法。
邹都[2]（2007）在《以Minkowski减法研究凸体包含测度的新方法》文中提出本论文以凸体和星体为研究对象,主要涉及如下几个方面的内容:1.定长线段在斜柱体内的运动测度与超平行体基本区域的格型Buffon-Ren问题本部分内容隶属积分几何学,所做的工作是利用积分几何的基本理论求解了线段在斜柱体和超平行体内包含测度积分公式,并将所得结果应用到了超平行体基本区域的格型Buffon-Ren问题。2.以Minkowski减法研究紧凸集在凸体内包含测度的新方法本部分内容隶属积分几何学中包含测度问题的理论研究。所做工作主要如下:（1）在欧氏空间积分几何学和凸几何的基础理论上,提出了以Minkowski减法研究紧凸集在凸体内包含测度的新方法并阐释了该方法的基本原理;（2）作为例证,借助于该方法给出了一些包含测度及平移包含测度公式,并解决了平移包含测度极值问题;（3）将该方法应用于线段在凸体内包含测度的研究,获得了几个新的一般积分公式,并利用所得结果解决了高维空间中线段在椭球体内包含测度一般积分公式的求解问题;（4）利用凸几何学工具对所提出的方法进行了较为深入的讨论,并获得了紧凸集在凸体内平移包含测度的体积表达公式;（5）作为应用,获得了同维单形在凸体内平移包含测度的一个整体性质,该性质是线段在凸体内包含测度与该凸体弦幂积分关系的推广。3.星体几何不等式的多元型抽象形式本部分内容隶属对偶Brunn-Minkowski理论,所做的工作是在作者提出的星体的径向乘法、径向幂运算和多元型对偶混合体积等概念的基础上,利用积分的方法获得了星体对偶Minkowski不等式的多元型版本以及星体相关几何不等式的抽象形式,并讨论了星体组的径向平均体的几何性质及其应用。
蒋联源[3]（2007）在《凸壳算法及其应用研究》文中研究说明凸壳在模式识别、图象处理、图形学和人工智能等方面有广泛的应用,许多实际问题都可以归纳成凸壳问题求解。本文对凸壳和凸壳直径计算进行了研究,提出了相关算法,同时对凸壳在轮廓匹配和高密度点集物碰撞检测中的应用进行了探讨,理论分析和实验结果验证算法的可行性和有效性。本文工作主要从以下六个方面展开:（1）实时凸壳算法。由于正切线算法计算凸壳时对新加入实时点进行编号的局限性,提出一种实时凸壳算法。算法通过极值点将平面划分为若干区域,根据实时点所在区域,确定受影响的单调段,对受影响单调段上的顶点通过正切线算法重新计算,以横坐标作为新加入点的编号实现自动编号,最终由新的单调段得到新的凸壳。（2）给定平面点集凸壳算法。将正切线算法应用到给定平面点集凸壳的计算中,通过凸壳的极值点定义了凸壳的单调段,并将点集分成若干个区域,对于点集中的点,若该点落在由各单调段所围成的区域内部,则该点一定不是凸壳上的点;计算落于其它区域中的点,只需通过该点与它所在区域的原单调段进行计算得到新单调段,从而得到给定平面点集的凸壳。（3）基于凸多边形顶点间距离性质的凸多边形直径算法。平面点集的直径问题可以转化为求凸多边形直径问题,论文研究了凸多边形的直径计算,得出凸多边形上顶点间距离关系的一些性质,提出一种基于顶点间距离性质的凸多边形直径算法,利用这些性质可减少大量夹角符号计算。（4）基于凸多边形顶点序列到边的距离单调性的凸多边形直径算法。论文研究了凸多边形顶点序列到边的距离单调性,算法根据这种单调性通过折半查找实现对首个对跖点对的查找,实现了一种快速的凸多边形直径算法。（5）凸壳在轮廓匹配中的应用研究。轮廓匹配是计算机视觉研究中的一个重要课题,论文研究了平移旋转和伸缩变换下的轮廓匹配问题,得出了重心是平移旋转和伸缩变换下的不变量,根据重心这一不变量计算变换中的平移量、旋转角度和缩放因子,实现轮廓匹配。（6）凸壳在高密度点集物碰撞检测中的应用研究。虚拟环境已成为计算机科学的一个重要研究领域,虚拟对象之间的碰撞检测是其关键问题之一。论文对二维平面对象碰撞检测问题进行研究,将凸壳应用到高密度点集物碰撞检测中,提出了一种基于凸壳包围盒的高密度点集物碰撞检测算法。首先计算待碰撞点集物的凸壳,通过对凸壳进行求交运算,若不相交,两点集物未发生碰撞;若相交,在两凸壳的交集区域中寻找碰撞点集。论文中的算法取得了如下结果:（1）实时凸壳算法实现了对实时点的自动编号,对每一个新增实时点最多只需对2个单调段进行计算,提高了运算效率。（2）对静态凸壳的计算,落于由各单调段所围成的区域外的点,只需跟该点所在区域的原单调段上的顶点进行计算,减少了处理的点,提高了算法执行速度。（3）利用顶点间距离关系的性质提高了夹角符号序列法的计算速度,空间复杂度为O（n）,存储效率高。（4）查找首个对跖点对所需时间复杂度为O（logn）,整个算法所需辅助空间为常量,时间和空间两方面都优于同类算法,该算法效率高、可靠性好、实用性较强。（5）轮廓匹配算法时间和空间复杂度均为O（n）,匹配可靠,效率高,具有一定实用性。（6）高密度点集物碰撞检测算法简单、高效、可靠、实用。
朱海燕[4]（2005）在《GIS空间分析方法在热带气旋研究中的应用》文中认为在全球热带气旋（Tropical Cyclone,以下简称TC）生成区中,西北太平洋的发生频率最高,占全球总数的1/3以上,同时西北太平洋上的台风强度也是全球最强。我国是世界上遭受TC影响最为频繁和严重的国家之一。因此研究TC的发生发展,准确预报TC活动对于防灾减灾具有重要的意义。也因而TC研究的重要性长期得到重视。 由于TC活动的复杂性,人们不断地探索新技术、新方法在TC预报和影响分析中的应用。在本文中,作者对基于GIS空间分析技术的TC预报和TC过程降水的空间插值问题进行了探索研究,分别提出了:1) 面积指数的相似度概念和算法,以及基于这种相似性测度的TC预报方法;2) 基于凸包和Voronoi多边形技术的TC过程降水的数据插补和空间插值方法。 TC活动的路径趋向的准确预报一直是一个困难的问题,为此气象学家们建立了各种预报方法,包括动力模型、统计模型、动力一统计相结合的模型等等。在TC活动的统计预报中,基于相似性的预报是一类重要的技术,于是本文基于GIS技术进行了相似性预报的探索研究,我们用路径的几何相似扩展了气象学中地理相似的概念,并在此基础上提出了面积指数的路径相似测度方法,就是用一定时段内实时路径和历史路径所包围的面积与某一参照面积的比值测度来表示历史路径和实时路径在该时段内相似程度,然后根据相似程度选择最为相似的前n条TC路径建立预报模型,试验研究表明该模型对于非异常的路径具有较高的精度。 TC常常带来大范围的强降水,在使用GIS技术研究过程降水的分布和影响时,需要使用空间插值技术。目前人们对于空间插值技术的研究很多,大多数GIS软件提供了空间插值的工具,例如ArcGIS中的空间分析工具箱就提供多种空间插值方法包括克里格方法、倒数距离加权法、样条函数等。但是我们发现这些插值方法在应用于TC过程降水中存在一些需要解决的问题:1) 台风降水的显着特点是存在明确的空间范围,即降水区域和非降水区域之间存在一条明显的分界线,因此需要确定降水的0值边界,而GIS中的空间插值方法没有考虑这一情况,这样如果不加区分地使用GIS工具箱中提供的插值方法,可能会带来不正确的的降水表示——例如无降水记录的区域被插值成有降水分布。我们将其称为第一类的数据完整性问题。2) 在数据库的建立和数据分析过程中我们发现,在降水分布的范围内存在一些测站没有降水记录的情况,仅仅根据数据记录无法判别是由于这一测站本来就没有降水发生,还是因为漏测或无需上报降水数据而使
殷艾文[5]（2003）在《以凸包为工具求解组合几何题》文中认为
二、以凸包为工具求解组合几何题（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、以凸包为工具求解组合几何题（论文提纲范文）
（1）基于凸壳的半监督聚类算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 半监督学习简介 |
| 1.2 选题背景及其研究意义 |
| 1.3 半监督聚类算法的国内外研究现状 |
| 1.4 论文主要研究内容及章节安排 |
| 2 半监督聚类理论基础 |
| 2.1 聚类相关的概念及原理 |
| 2.1.1 簇的概念 |
| 2.1.2 簇的不同类型 |
| 2.1.3 常见的聚类类型 |
| 2.2 半监督聚类理论 |
| 2.2.1 基于限制的方法 |
| 2.2.2 基于距离测度的方法 |
| 2.3 经典聚类算法理论及实现 |
| 2.3.1 经典无监督聚类算法 |
| 2.3.2 经典半监督聚类算法 |
| 2.4 聚类质量度量 |
| 2.4.1 使用凝聚度和分离度度量 |
| 2.4.2 使用相似度度量 |
| 2.5 本章小结 |
| 3 凸壳理论及算法实现 |
| 3.1 凸壳的定义及凸壳问题的提出 |
| 3.2 凸壳理论的研究现状 |
| 3.2.1 凸壳应用的研究现状 |
| 3.2.2 凸壳算法的研究现状 |
| 3.3 几种常见凸壳求解算法的理论及实现 |
| 3.3.1 卷包裹法 |
| 3.3.2 格雷厄姆法 |
| 3.3.3 QuickHull 算法 |
| 3.4 凸壳算法的时间复杂度实验 |
| 3.4.1 实验数据说明 |
| 3.4.2 实验结果及说明 |
| 3.5 本章小结 |
| 4 SCBCH 算法的设计与实现 |
| 4.1 SCBCH 算法的提出 |
| 4.2 SCBCH 算法的流程 |
| 4.3 SCBCH 算法的验证实验 |
| 4.3.1 实验说明 |
| 4.3.2 相关数据说明 |
| 4.3.3 实验结果及分析 |
| 4.4 本章小结 |
| 5 总结和展望 |
| 5.1 全文总结 |
| 5.2 下一步工作 |
| 参考文献 |
| 致谢 |
| 个人简历 |
| 在学期间发表的学术论文 |
（2）以Minkowski减法研究凸体包含测度的新方法（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 综述 |
| 1.2 问题的提出及研究现状分析 |
| 1.2.1 定长线段在斜柱体内的包含测度与Buffon-Ren 问题的求解 |
| 1.2.2 一般凸集在凸体内的平移包含测度及包含测度问题 |
| 1.2.3 星体几何不等式的多元抽象问题 |
| 1.3 本论文所作的工作 |
| 1.4 研究目标 |
| 1.5 本研究的创新之处 |
| 1.6 本论文的内容安排 |
| 第二章 定长线段在斜柱体内的包含测度与Buffon-Ren 问题的求解 |
| 2.1 引言及问题的提出 |
| 2.2 预备知识 |
| 2.2.1 欧氏空间中的积分几何理论概论 |
| 2.2.2 本文的一则约定 |
| 2.2.3 限弦函数及限弦投影函数 |
| 2.2.4 斜投影 |
| 2.3 主要结果 |
| 2.3.1 定长线段在斜柱体内的运动测度公式 |
| 2.3.2 定长线段在超平行体内的运动测度公式 |
| 2.3.3 运动测度公式在Buffon-Ren 问题中的应用 |
| 2.4 主要结果的证明 |
| 2.4.1 定理2.1 的证明 |
| 2.4.2 定理2.2 的证明 |
| 第三章 以Minkowski 减法研究凸体包含测度的新方法 |
| 3.1 引言 |
| 3.2 预备知识 |
| 3.2.1 一般集合的Minkowski 加法及其相关性质 |
| 3.2.2 凸集、凸集的Minkowski 加法及其相关性质 |
| 3.2.3 Minkowski 减法、凸集Minkowski 减法及其相关性质 |
| 3.2.4 凸体与其位似体的Minkowski 减法集的性质 |
| 3.3 一集合可被另一集合平移包含与Minkowski 减法集的关系 |
| 3.3.1 包含测度的定义 |
| 3.3.2 平移包含测度的Minkowski 减法集的体积表达公式 |
| 3.3.3 几则应用 |
| 3.4 线段在凸体内包含测度的新积分公式 |
| 3.4.1 线段在凸体内包含测度的新公式 |
| 3.4.2 线段在椭球体内的包含测度积分公式 |
| 3.4.3 线段在超平行体内的包含测度积分公式 |
| 3.5 Minkowski 减法集的结构与平移包含测度公式的进一步细化 |
| 3.5.1 Minkowski 减法集的结构 |
| 3.5.2 平移包含测度公式的进一步细化 |
| 3.6 同维单形在凸体内平移测度的一个整体性质 |
| 第四章 星体几何不等式的多元抽象推广 |
| 4.1 引言 |
| 4.2 理论准备 |
| 4.3 对偶Minkowski 不等式的多元拓广形式 |
| 4.4 对偶Brunn-Minkowski 型不等式的抽象形式 |
| 4.5 星体组的平均 |
| 4.6 星体组加权幂平均体的应用 |
| 第五章 展望 |
| 参考文献 |
| 致谢 |
| 详细摘要 |
（3）凸壳算法及其应用研究（论文提纲范文）
| 中文摘要 |
| ABSTRACT |
| 第一章 绪论 |
| 1.1 凸壳的基本概念 |
| 1.2 凸壳算法及其应用的研究现状 |
| 1.3 本文主要工作和章节结构 |
| 第二章 凸壳算法 |
| 2.1 一种实时凸壳算法 |
| 2.1.1 正切线算法概述 |
| 2.1.2 实时凸壳算法 |
| 2.1.3 复杂度分析 |
| 2.1.4 小结 |
| 2.2 一种给定平面点集凸壳算法 |
| 2.2.1 给定平面点集的凸壳算法 |
| 2.2.2 复杂度分析 |
| 2.2.3 小结 |
| 第三章 凸壳直径计算 |
| 3.1 基于顶点间距离性质的凸多边形直径算法 |
| 3.1.1 引言 |
| 3.1.2 夹角符号序列法概述 |
| 3.1.3 凸多边形直径算法 |
| 3.1.4 复杂度分析 |
| 3.1.5 实验结果 |
| 3.1.6 小结与讨论 |
| 3.2 基于距离单调性的凸多边形直径算法 |
| 3.2.1 引言 |
| 3.2.2 PREPARATA-SHAMOS 算法概述 |
| 3.2.3 直径算法 |
| 3.2.4 复杂性分析 |
| 3.2.5 实验结果与讨论 |
| 第四章 凸壳的应用研究 |
| 4.1 凸壳在轮廓匹配中的应用研究 |
| 4.1.1 引言 |
| 4.1.2 轮廓匹配算法 |
| 4.1.3 复杂度分析 |
| 4.1.4 实验结果 |
| 4.1.5 小结与讨论 |
| 4.2 凸壳在高密度点集物碰撞检测中的应用研究 |
| 4.2.1 引言 |
| 4.2.2 碰撞检测原理 |
| 4.2.3 高密度点集物碰撞检测算法 |
| 4.2.4 复杂度分析及实验结果 |
| 4.2.5 小结与讨论 |
| 第五章 总结与进一步的工作 |
| 5.1 全文总结 |
| 5.2 进一步工作 |
| 参考文献 |
| 攻读硕士学位期间的科研及获奖情况 |
| 致谢 |
（4）GIS空间分析方法在热带气旋研究中的应用（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第一章 引论 |
| 1.1 热带气旋研究的意义 |
| 1.2 GIS在热带气旋研究中的应用 |
| 1.3 本文的工作 |
| 1.4 论文的结构 |
| 第二章 热带气旋相似路径预报研究 |
| 2.1 相似路径研究方法 |
| 2.2 基于GIS空间相似的方法——面积指数法 |
| 2.2.1 路径相似概念 |
| 2.2.2 面积指数法 |
| 2.2.3 实现方法 |
| 2.3 空间相似的TC路径预报方法 |
| 2.4 实例研究 |
| 实例一：登陆上海台风路径预报 |
| 实例二：Babe热带气旋不同时间段路径预报 |
| 2.5 小结 |
| 第三章 热带气旋降水空间分布研究 |
| 3.1 空间插值方法与降水场的有关问题 |
| 3.1.1 空间插值与降水应用 |
| 3.1.2 空间插值方法在降水应用中的缺陷 |
| 3.2 降水数据完整性——凸包方法 |
| 3.2.1 技术路线 |
| 3.2.2 凸包算法 |
| 3.2.3 数据插补：最大最小距离 |
| 3.3 边界效应——Voronoi多边形 |
| 3.3.1 Voronoi多边形——搜索降水区边界 |
| 3.3.2 技术路线 |
| 3.3.3 构造插值完整数据集 |
| 3.4 实例研究 |
| 实例一：195804台风降水时空分布 |
| 实例二：195114台风降水时空分布 |
| 3.5 小结 |
| 第四章 总结与讨论 |
| 4.1 总结 |
| 4.2 需要进一步讨论的问题 |
| 参考文献(References) |
| 后记 |
（5）以凸包为工具求解组合几何题（论文提纲范文）
| 1 凸图形与凸包 |
| 2 典型例子分析 |
| 2.1 以凸包为分类工具求解组合几何中的最值问题 |
| 2.2 以凸包为分类工具求解组合几何中的存在性问题 |
四、以凸包为工具求解组合几何题（论文参考文献）
- [1]基于凸壳的半监督聚类算法研究[D]. 王桂亮. 中国海洋大学, 2011(04)
- [2]以Minkowski减法研究凸体包含测度的新方法[D]. 邹都. 武汉科技大学, 2007(04)
- [3]凸壳算法及其应用研究[D]. 蒋联源. 广西师范大学, 2007(05)
- [4]GIS空间分析方法在热带气旋研究中的应用[D]. 朱海燕. 华东师范大学, 2005(05)
- [5]以凸包为工具求解组合几何题[J]. 殷艾文. 数学通讯, 2003(01)