凸包及其在acm-icpc中的应用

《凸包及其在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中的每个点都被压入