凸包及其在ACMICPC中应用.docVIP

凸包及其在ACM-ICPC中的应用 许山蒙，陈 强，杨 彬 （山东理工大学 计算机科学与技术学院，山东 淄博 255049） 摘 要：文章对计算几何中的凸包问题进行了讨论。对于凸包的概念与性质进行了描述，并对各种求凸包的方法进行了分析和比较，重点对Graham扫描法和其所用到的极角排序进行了详细描述。通过对凸包的算法设计、代码实现等步骤的分析，对传统算法的时间、空间复杂性进行了优化，并通过两个POJ上的例子说明了凸包问题在程序设计中的应用。 关键词：凸包；计算几何；极角排序；Graham扫描法 中图分类号：TP301.6 文献标识码：A Convex hull and its application in ACM-ICPC XU Shan-meng，CHEN Qiang，YANG Bin (School of Computer Science and Technology University of Technology, Zibo 255049, China) Abstract：described. And we analysised and compared various kinds of ways to computing convex hulls. The algorithm Graham’s Scan and pole angle sorting were described in detail. According to the analysis of algorithm design and code implementation of convex hull, the time and space complexity of traditional algorithm were optimized. And the application of convex hull in programing have been also expounded by two example of POJ. Key words：’s scan 1 凸包的概念及其性质 计算几何学是计算机科学的一个分支，专门研究那些用来解决几何问题的算法。在现代工程与数学中，计算机图形学、机器人学等领域中，计算几何学都发挥了重要作用。凸包问题是计算几何的基本问题，分为离散点集凸包和多边形凸包两类。在求取点集凸包时，不仅要从大量的离散点中判断出凸包顶点，还要得到这些点的连接关系，从而得到一个凸包。本文重点讨论基于平面点集的凸包的算法与应用。对于二维的离散点集，它们的凸包表现为一个凸多边形。随着凸包问题的提出，各种凸包的求法也相继被提出。其算法的时间复杂度和空间复杂度也一次次的被优化。 1.1凸包的概念 点集P的凸包，就是顶点取自于P，且包含 P 中所有点的那个唯一的凸多边形。 我们可以想象一下，点集P是在一个平面上钉的一些钉子，取来一根橡皮绳，撑开它围住所有的钉子，然后松开手。啪的一声，橡皮绳紧绷到钉子上，其长度也达到最小。此时，由橡皮绳围住的区域就是P的凸包。 1.2凸包的性质 1）点集P所有的点都在凸包内部或是在凸包上。 2）任意选取凸包的一条边，由这条边确定一条直线，那么点集P中除了这条边的两个顶点外，其他所有的点都在直线的同一侧。 3）点集P中距离最远的两点，必然是P的凸包的某两个顶点。而这个最远距离，就是凸包的直径。 2各种求凸包的方法 上世纪70年代以来本文重点介绍Graham扫描法 2.1增量法 在增量法中，首先对点从左到右进行排序，然后选取几个点形成初始凸包，然后不断引入新顶点，再对凸包进行更新。传统枚举法的时间复杂度为O(n3)，而增量法的时间复杂度为O(n2)。 2.2分治法 将n个点组成的集合划分为左右两个子集，分别包含最左边的一半点集和最右边的一半点集，并对子集的凸包进行递归计算，然根据对两个子集凸包的公切线进行合并。该算法时间复杂度为O(n lg n)。 2.3 Jarvis步进法 该算法采用了一种称为“打包”的技术来计算一个点集的凸包。以某极值点作为开始点，根据其他点都位于相邻顶点连线同侧的原则，找到所有的顶点。其时间复杂度为O(nh)，其中h为凸包顶点数。 2.4 Graham扫描法 通过设置一个关于凸包候选点的栈S来解决凸包问题。点集P中的每个点都被压入栈一次，非凸包顶点的点最终将被弹出。算法终止时，S中仅包含凸包CH(P)的顶点，其顺序为各点在凸包上出现的逆时针方向排序的序列。其时间复杂度为O(n lg n)。具体步骤如下： 1) 找到P的左下角的点，即y值最小的点（若y相等，则要求x最小），把它放在序列的首位置，标记为P0。如图2.4.1。 2) 然后，对其他的