多核架构下计算凸壳的并行算法  

Parallel Algorithm for Computing Convex Hulls in Multi-processor Architecture

作　　者：颜坚[1] 毕硕本[2] 汪大[1] 郭忆[2] 

机构地区：[1]南京信息工程大学计算机与软件学院,南京210044 [2]南京信息工程大学遥感学院,南京210044

出　　处：《计算机科学》2013年第2期16-19,57,共5页Computer Science

基　　金：国家自然科学基金项目(41071253);江苏省六大人才高峰项目(20080249)资助

摘　　要：改进了周培德的Z3-2算法,提出一种在多核架构下计算平面点集凸壳的并行算法。用"颜氏距离"来数字化平面上点与有向线段的位置关系,减少了计算次数和时间。进一步将原算法中比较耗时的两个过程分别在O(1)的时间复杂度内进行迭代分解,即当原问题规模大于给定阈值时,将原问题分解为若干个独立的子问题,若所得子问题的规模仍大于给定阈值,则再对子问题进行分解;所有子问题被加入并行任务组进行并行求解以充分利用多核处理器的并行计算资源。给出了算法的正确性说明,实验结果也表明本算法稳定高效。This paper Improved the Z3-2 algorithm proposed by ZHOU Pei-de, and proposed a parallel algorithm for computing the convex hulls of planar point set in multi-processor architecture. The times and duration of calculation were reduced by digitizing the positional relationship between a point and a directed line segment on plane with ＂Yan＇s distance＂. Further, the two progresses were decomposed iteratively which are the foremost time-consuming parts in the algorithm within the complexity of 0（1）. That is, the original task is decomposed into several sub-tasks when its scale is greater than a given threshold and then decompose any of the sulytasks if its scale is still greater than the threshold. All sub-tasks will be executed in parallel from the parallel task group to take full advantage of the parallel computation re- sources of the muhi-processor. The correctness of the algorithm was discussed. The experiment results show that the algorithm is efficient and stable.

关 键 词：凸壳 并行计算 多核 颜氏距离 

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