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

Abstract: 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 O(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 sulrtasks 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 resources of the multi-processor. The correctness of the algorithm was discussed. The experiment results show that the algorithm is efficient and stable.

Key words: Convex hull, Parallel computing, Multi core, Yan's distance