凸包及其在CM-ICPC中的应用.doc

凸包及其在ACM-ICPC中的应用 许山蒙，陈 强，杨 彬 （山东理工大学 计算机科学与技术学院，山东 淄博 255049） 摘 要：文章对计算几何中的凸包问题进行了讨论。对于凸包的概念与性质进行了描述，并对各种求凸包的方法进行了分析和比较，重点对Graham扫描法和其所用到的极角排序进行了详细描述。通过对凸包的算法设计、代码实现等步骤的分析，对传统算法的时间、空间复杂性进行了优化，并通过两个POJ上的例子说明了凸包问题在程序设计中的应用。 关键词：凸包；计算几何；极角排序；Graham扫描法 中图分类号：TP301.6 文献标识码：A 收稿日期：2011 收稿日期：2011-01-20 基金项目：基金项目类别(项目编号) 作者简介：许山蒙（1990-）, 男, 大学生. E-mail：jamblue@ Convex hull and its application in ACM-ICPC XU Shan-meng，CHEN Qiang，YANG Bin (School of Computer Science and Technology, Shandong University of Technology, Zibo 255049, China) Abstract：In this paper, the problem of convex hull in computational geometry was discussed. The concept and character of convex hull were 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：convex hull; computational geometry; polar angle sorting; Graham’s scan 1 凸包的概念及其性质 计算几何学是计算机科学的一个分支，专门研究那些用来解决几何问题的算法。在现代工程与数学中，计算机图形学、机器人学等领域中，计算几何学都发挥了重要作用。凸包问题是计算几何的基本问题，分为离散点集凸包和多边形凸包两类。在求取点集凸包时，不仅要从大量的离散点中判断出凸包顶点，还要得到这些点的连接关系，从而得到一个凸包。本文重点讨论基于平面点集的凸包的算法与应用。对于二维的离散点集，它们的凸包表现为一个凸多边形。随着凸包问题的提出，各种凸包的求法也相继被提出。其算法的时间复杂度和空间复杂度也一次次的被优化。 1.1凸包的概念 点集P的凸包CH(P)，就是顶点取自于P，且包含 P 中所有点的那个唯一的凸多边形。 我们可以想象一下，点集P是在一个平面上钉的一些钉子，取来一根橡皮绳，撑开它围住所有的钉子，然后松开手。“啪”的一声，橡皮绳紧绷到钉子上，其长度也达到最小。此时，由橡皮绳围住的区域就是P的凸包。 1.2凸包的性质 1）点集P所有的点都在凸包内部或是在凸包上。 2）任意选取凸包的一条边，由这条边确定一条直线，那么点集P中除了这条边的两个顶点外，其他所有的点都在直线的同一侧。 3）点集P中距离最远的两点，必然是P的凸包的某两个顶点。而这个最远距离，就是凸包的直径。 2各种求凸包的方法 上世纪70年代以来，不少学者提出了点集凸包的计算方法，较为经典的有Graham扫描法、Jarvis步进法、增量法、分治法等。本文重点介绍Graham扫描法。 2.1增量法 在增量法中，首先对点从左到右进行排序，然后选取几个点形成初始凸包，然后不断引入新顶点，再对凸包进行更新。传统枚举法的时间复杂度为O(n3)，而增量法的时间复杂度为O(n2)。 2.2分治法 将n个点组成的集合划分为左右两个子集，分别包含最左边的一半点集和最右边的一半点集，并对子集的凸包进行递归计算，然根据对两个子