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

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

提出了在基于有序简单多边形的平面点集凸包快速求取算法基础上改进的并行算法,该算法的时间复杂度达到了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.