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

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

作　　者：周启海[1] 黄涛[1] 吴红玉[2] 

机构地区：[1]西南财经大学信息技术应用研究所,成都610074 [2]西南财经大学经济信息工程学院,成都610074

出　　处：《计算机科学》2008年第2期232-234,241,共4页Computer Science

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

关 键 词：同构化 机群 凸壳 并行算法 双群 双域 四向 

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