【作者】 陈平；

【导师】 汪国昭；

【作者基本信息】 浙江大学 ， 应用数学， 2006， 硕士

【摘要】 计算几何是理论计算机科学领域中极有生命力的子领域，其研究成果已在计算机图形学、化学、统计分析、模式识别、地理数据库以及其他许多领域中得到了广泛的应用。如何为各种应用提供有效的基础算法以及理论依据，一直是国内外学者研究的方向。本文从以下三个方面来讨论计算几何中的若干基本问题： 第一、本文证明了“每个多边形至少有三个凸顶点”的定理，这扩展了“每个多边形至少有一个凸顶点”的定理。 第二、本文采用逐步删除点集的方法，对平面点集进行预处理，使得改进后的算法能够避免极值点重合的问题，有效地减少构建凸包的点。 第三、本文在“欧拉-西格纳”问题的基础上进一步考虑三角剖分方法数与对角线的关系。首先分析五边形、六边形以及七边形在减少一些对角线后可能的三角剖分方法数，然后提出了多边形三角剖分方法数“次上限”的概念，并给出了“次上限”的计算公式。更多还原

【Abstract】 Computational geometry is a vital sub-domain in the theoretical computer science domain, its research result has already gotten an extensive application in the computer graphics, the chemistry, the statistics, the pattern recognition, the geographic database and other many domains. How to provide valid algorithms and theories for various application, have been the direction that the domestic and international scholar study. This article discusses some basic problems on computational geometry as following:The first, this article proves the theory of "each polygon has three convex vertex at least", which expands the theory of "each polygon has a convex vertex at least".The second, this article pretreat the planar point set by deleting points gradually, which make the improved algorithm avoid the problem that extremity vertices being , and reduce points efficiently.The third, this article discusses the relation between the number of triangulation and diagonal basing on "Euler-Segner problem" It analyzing the number of triangulation when a polygon such as pentagon ,hexagon and heptagon reduce some diagonal, then put forward the concept "sub-upper limit" of the number of a polygon triangulation , and gives the calculation formula of "sub-upper limit".更多还原