基于双群双域四向水平倾角最小化圈绕的凸壳并行新算法

本文针对现行凸壳算法(诸如:串行类的卷包裹凸壳算法、格雷厄姆凸壳算法等,并行类的折半分治凸壳算 法、快速凸壳算法等)效率不高的缺点,根据同构化凸壳构造基本定理,利用工作站机群优点,提出了效率更高的双群(即:其机群分为2个子机群)、双域(即:其数据分布域分为2个子分布域)、四向(即:其每个子分布域内凸壳顶点的寻找方向均各自为顺时针、逆时针2个寻找方向)水平倾角最小化圈绕的凸壳并行新算法.

A New Parallel Algorithm for Finding Convex Hull Based on Minimum Lever Pitch Coiling with 2-Clnsters, 2-Domains and 4-Directions

In this paper,comment on the lower efficiency shortcomings of representative both series algorithms for finding convex hull(for example:Gift wrapping convex hull algorithm,Graham scan convex hull algorithm,and so on)and parallel algorithms for finding convex hull(for example:Half-dividing convex hull algorithm,Rapid convex hull algorithm,and so on),and according to the isomorphic fundamental theorem of the convex hull construction and using the advantages of COW(Cluster of workstation),a more efficient new parallel algorithm to find a convex hull is given.The general characters of the new parallel algorithm are:1)its COW is combined with two sub-clusters;2)its domain is divided into two sub-domains;3)its seeking directions of coiling with a minimum lever pitch in every sub-domain are along with two ways(i.e.clockwise direction,and anti clockwise direction)separately.