一种改进的构建凸包的分治算法  

An Improved Divide and Conquer Algorithm for Computing the Convex Hull

作　　者：刘新 刘任任[1] 

机构地区：[1]湘潭大学信息工程学院,湖南湘潭411105

出　　处：《计算机工程与科学》2006年第8期63-65,共3页Computer Engineering & Science

基　　金：湖南省自然科学基金资助项目(03JJY3099)

摘　　要：本文为构建离散点的凸包提出了一种改进的分治算法,它在查找每一个凸包顶点的同时,通过去除若干非凸包顶点来迅速减小问题的规模。本文对该算法的正确性给出了严格的证明。An improved divide and conquer algorithm for computing the convex hull of a finite set of points, which exclude the points impossible to be on the hull to reduce the time complexity when it searches the apexes of the convex hull, is presented. The correctness of the algorithm is proved strictly.

关 键 词：凸包 平面散点 分治法 FLOYD算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]