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

Parallel Algorithm for Computing Convex Hulls in Multi-processor Architecture

改进了周培德的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.