平面点集凸包的并行算法研究  

Parallel convex hull algorithm of planar point set based on PC cluster

作　　者：郝小柱[1] 胡祥云[1] 戴光明[2] 张荣[1] 程红杰[1] 

机构地区：[1]中国地质大学地球物理与空间信息学院,湖北武汉430074 [2]中国地质大学计算机学院,湖北武汉430074

出　　处：《计算机应用》2005年第10期2462-2464,共3页journal of Computer Applications

摘　　要：提出了在基于有序简单多边形的平面点集凸包快速求取算法基础上改进的并行算法,该算法的时间复杂度达到了O(n)。在PC机互连构成的机群(COW)并行计算系统上以消息传递方式执行该算法,通过与原串行算法对比验证了该算法的可行性、正确性和高效性。A new parallel algorithm was proposed by combining improved fast convex hull algorithm of planar point set based on sorted simple polygon in this paper. The worst-case time complexity of the algorithm was O（n） . The algorithm used in COW parallel computing system and MPI parallel environment. Compared with the original serial algorithm, this method was viable, accurate and highly efficient.

关 键 词：点集凸包 并行算法 机群 消息传递界面 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]