欢迎来到天天文库
浏览记录
ID:15445463
大小:213.00 KB
页数:7页
时间:2018-08-03
《凸包及其在acm-icpc中的应用》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、凸包及其在ACM-ICPC中的应用许山蒙,陈强,杨彬(山东理工大学计算机科学与技术学院,山东淄博255049)摘要:文章对计算几何中的凸包问题进行了讨论。对于凸包的概念与性质进行了描述,并对各种求凸包的方法进行了分析和比较,重点对Graham扫描法和其所用到的极角排序进行了详细描述。通过对凸包的算法设计、代码实现等步骤的分析,对传统算法的时间、空间复杂性进行了优化,并通过两个POJ上的例子说明了凸包问题在程序设计中的应用。关键词:凸包;计算几何;极角排序;Graham扫描法中图分类号:TP301.6文献标识码:A收稿日期:2011-01-
2、20基金项目:基金项目类别(项目编号)作者简介:许山蒙(1990-),男,大学生.E-mail:jamblue@foxmail.comConvexhullanditsapplicationinACM-ICPCXUShan-meng,CHENQiang,YANGBin(SchoolofComputerScienceandTechnology,ShandongUniversityofTechnology,Zibo255049,China)Abstract:Inthispaper,theproblemofconvexhullincomputat
3、ionalgeometrywasdiscussed.Theconceptandcharacterofconvexhullweredescribed.Andweanalysisedandcomparedvariouskindsofwaystocomputingconvexhulls.ThealgorithmGraham’sScanandpoleanglesortingweredescribedindetail.Accordingtotheanalysisofalgorithmdesignandcodeimplementationofconv
4、exhull,thetimeandspacecomplexityoftraditionalalgorithmwereoptimized.AndtheapplicationofconvexhullinprograminghavebeenalsoexpoundedbytwoexampleofPOJ.Keywords:convexhull;computationalgeometry;polaranglesorting;Graham’sscan1凸包的概念及其性质计算几何学是计算机科学的一个分支,专门研究那些用来解决几何问题的算法。在现代工程与数
5、学中,计算机图形学、机器人学等领域中,计算几何学都发挥了重要作用。凸包问题是计算几何的基本问题,分为离散点集凸包和多边形凸包两类。在求取点集凸包时,不仅要从大量的离散点中判断出凸包顶点,还要得到这些点的连接关系,从而得到一个凸包。本文重点讨论基于平面点集的凸包的算法与应用。对于二维的离散点集,它们的凸包表现为一个凸多边形。随着凸包问题的提出,各种凸包的求法也相继被提出。其算法的时间复杂度和空间复杂度也一次次的被优化。1.1凸包的概念点集P的凸包CH(P),就是顶点取自于P,且包含P中所有点的那个唯一的凸多边形。我们可以想象一下,点集P是在
6、一个平面上钉的一些钉子,取来一根橡皮绳,撑开它围住所有的钉子,然后松开手。“啪”的一声,橡皮绳紧绷到钉子上,其长度也达到最小。此时,由橡皮绳围住的区域就是P的凸包。1.2凸包的性质1)点集P所有的点都在凸包内部或是在凸包上。2)任意选取凸包的一条边,由这条边确定一条直线,那么点集P中除了这条边的两个顶点外,其他所有的点都在直线的同一侧。3)点集P中距离最远的两点,必然是P的凸包的某两个顶点。而这个最远距离,就是凸包的直径。2各种求凸包的方法上世纪70年代以来,不少学者提出了点集凸包的计算方法,较为经典的有Graham扫描法、Jarvis步
7、进法、增量法、分治法等。本文重点介绍Graham扫描法。2.1增量法在增量法中,首先对点从左到右进行排序,然后选取几个点形成初始凸包,然后不断引入新顶点,再对凸包进行更新。传统枚举法的时间复杂度为O(n3),而增量法的时间复杂度为O(n2)。2.2分治法将n个点组成的集合划分为左右两个子集,分别包含最左边的一半点集和最右边的一半点集,并对子集的凸包进行递归计算,然根据对两个子集凸包的公切线进行合并。该算法时间复杂度为O(nlgn)。2.3Jarvis步进法该算法采用了一种称为“打包”的技术来计算一个点集的凸包。以某极值点作为开始点,根据其
8、他点都位于相邻顶点连线同侧的原则,找到所有的顶点。其时间复杂度为O(nh),其中h为凸包顶点数。2.4Graham扫描法通过设置一个关于凸包候选点的栈S来解决凸包问题。点集P中的每个点都被压入
此文档下载收益归作者所有