（此页为外封面，由专业复印室制作）分类号：密级：UDC：中国地质大学硕士学位论文金字塔凸壳算法的研究与实现硕士生：张忠武学科专业：计算机软件与理论指导教师：吴信才所在学院：信息工程学院二○一○年五月学校代码：10491研究生学号：120070899中国地质大学硕士学位论文金字塔凸壳算法的研究与实现硕士生：张忠武学科专业：计算机软件与理论指导教师：吴信才教授二○一○年五月ADissertationSubmittedtoChinaUniversityofGeosciencesfortheMasterDegreeofEngineeringResearchonandRealizationofPyramidHYPERLINK"http://dict.cnki.net/dict_result.aspx?searchword=%e5%87%b8%e5%a3%b3%e7%ae%97%e6%b3%95&tjType=sentence&style=&t=convex+hull+algorithm"AlgorithmforConvexHullMasterCandidate：ZhangZhongwuMajor：ComputerSoftwareandTheorySupervisor：PorefssorWuXincaiChinaUniversityofGeosciencesWuhan430074P.R.China中国地质大学（武汉）研究生学位论文原创性声明本人郑重声明：本人所呈交的硕士学位论文《金字塔凸壳算法的研究与实现》，是本人在导师的指导下，在中国地质大学（武汉）攻读硕士学位期间独立进行研究工作所取得的成果。论文中除已注明部分外不包含他人已发表或撰写过的研究成果，对论文的完成提供过帮助的有关人员已在文中说明并致以谢意。本人所呈交的硕士学位论文没有违反学术道德和学术规范，没有侵权行为，并愿意承担由此而产生的法律责任和法律后果。学位论文作者（签字）：日期：年月日作者简介张忠武，男，汉族，中共党员，1976年9月生，黑龙江省佳木斯市人。2007年9月至2010年6月就读于中国地质大学(武汉)研究生院攻读硕士学位，专业为计算机软件与理论，师从吴信才教授。硕士研究生期间完成高级计算机体系结构、计算机应用数学、算法设计与分析、计算几何及现代图形学等学位课程10门，空间数据库、地理信息系统技术与方法、科学方法论等选修课程5门，共修29个学分，总平成绩82分。先后获得校级优秀研究生、校级学术活动先进个人、优秀高等教育科学研究成果奖等奖项。攻读硕士期间主持的研究课题研究生学术探索与创新基金立项“大型GIS中平面海量散乱点集的新凸壳算法研究”(项目编号:CUGYJS0808)。课题类别：校级佳木斯大学科学技术研究项目“金字塔凸壳算法的研究与实现”(项目编号:L2009-141)。课题类别：校级攻读硕士期间参加的研究课题黑龙江省教育厅基金资助项目“煤矿安全监测支持系统研究”(项目编号:11511408)。课题类别：省级攻读硕士学位期间发表论文及书籍：△张忠武,吴信才.平面海量散乱点集凸壳算法[J].计算机工程,2009,35(9):43-45,48.△张忠武,吴信才.煤矿许用炸药检测中配气专家系统设计[J].微计算机信息,2009,25(6):38-40.△张忠武,史庆军.回溯算法在煤矿检验决策过程的应用[J].微计算机信息,2009,25(30):49-51.△参加撰写《面向对象程序设计（C++）》教材。副主编金字塔凸壳算法的研究与实现硕士生：张忠武导师：吴信才教授摘要计算几何是计算机算法研究领域中一个重要部分，而凸壳是计算几何中最普遍、最基本的一种结构，它被广泛地应用在模式识别、图象处理、图形学和人工智能等方面，在实际应用过程中，许多问题都可以转化成凸壳问题来加以解决。作为多年来计算机研究领域的热点问题，目前已有不少凸壳算法，但随着实际问题所涉及的信息量不断增长，并且传统凸壳算法在处理海量数据方面不能满足用户的需要，因此本文将寻求一种新的基于海量数据的凸壳算法。作为解决各领域问题的基本方法，凸壳算法为高性能应用系统的研究与实现提供了稳健的基础算法。基本算法是研究问题的基础，基本算法的优劣直接关系整个应用程序运行效率。不同的算法有不同的应用环境，常用的传统凸壳基本算法总的来说都不适合海量数据情况下使用，为此提出了一个易于实现的新凸壳算法－金字塔算法。快速优化算法是高性能凸壳算法的核心技术，旨在通过剔除海量数据中的更多无