【摘 要】
：
计算几何是理论计算机领域的一个重要方向，主要研究各种与几何有关的问题的算法设计和分析。本论文包含了作者近期所做的一些计算几何问题的结果，分为两部分:第一部分是关于三
【出 处】
：
中国科学院研究生院 中国科学院数学与系统科学研究院 中国科学院大学
论文部分内容阅读
计算几何是理论计算机领域的一个重要方向，主要研究各种与几何有关的问题的算法设计和分析。本论文包含了作者近期所做的一些计算几何问题的结果，分为两部分:第一部分是关于三角剖分问题的一些结果，包括第一章和第二章;第二部分是关于地图标号问题的一些结果，包括第三章和第四章。 点集（以及多边形）的三角剖分是计算几何领域的一种基本结构。三角剖分问题是计算几何，乃至整个理论计算机领域内的一个重要问题。它在计算机图形学，地理信息系统(GIS)，有限元方法以及计算流体力学等领域有着广泛的应用。 在第一章中，我们对于凸多边形给出了求最大权三角剖分的一个线性多项式时间近似方案(PTAS);在第二章中，我们改进了平面点集最大权三角剖分的上界，并且利用此上界把一个对平面点集求最大权三角剖分的Double-Spoke算法的近似比从6改进到4.238;最后我们还给出了对”semi-circular”型多边形求最大权三角剖分的时间复杂度为O(n2)的多项式时间算法。 地图标号问题是计算几何领域的另一重要问题，近年来在地理信息系统，图形学以及科学计算可视化等领域有着广泛的应用.地图标号问题已被ACM（美国计算机协会）计算几何任务小组列为离散计算几何领域的重要方向. 在第三章中，我们对于圆标号问题给出了一个近似比为3+(ε)的近似算法;在第四章中，我们对于三正方形标号问题给出了一个多项式时间算法。
其他文献
请下载后查看，本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
新课改下,体育与健康这门课程提出“坚持以健康为第一,促进学生健康发展,激发学生运动兴趣,培养学生终身体育的意识,以学生发展为中心,重视学生的主体地位,关注个体差异与不
在数学教学中,教师要以教材为依据,要从学生的生活经验和已有的知识背景出发,联系生活学数学,把生活经验数学化,数学问题生活化,体现“数学源于生活、寓于生活、用于生活”的
Baysian and empirical Bayes (EB) are important statistical methods and havebeen widely applied to many fields of statistics.This report consists of four Chapter
课堂教学的灵魂和课程实施的核心是学生参与课堂活动,学生只有主动参与课堂活动,才能更多地获取知识,更好地提高能力。小学生有效参与数学教学,需要教师充分了解小学生的个性
随着我国教育领域的不断改革发展,高职院校的教学目标开始与培养学生的综合能力为主,更重视对学生实践应用能力的培养.高职院校的英语教学也不例外,在素质教育改革之后,传统
传统的电子商务专业教育中与其他的专业教育无异,都是采用以教师讲授为主的教学模式,同时在学习的过程中也是以学生的个体学习为主,缺乏有效的沟通,对学生能力的提升也存在很
国家经理快速发展和社会水平提高的阶段当中,人才力量作为一种软实力和国家创新发展的主体力量已经得到了社会各界广泛的关注.况且在学校教育当中,学生们的思想和道德相较于