基于四群四域四向动态基线倾角最大化圈绕的凸壳并行新算法  

A New Parallel Algorithm for Finding Convex Hull Based on Maximum Pitch of the Dynamical Base Line Coiling with 4-Clusters,4-Domains and 4-Directions

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

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

出　　处：《计算机科学》2008年第3期240-243,共4页Computer Science

摘　　要：首先把基线倾角最大化圈绕凸壳串行算法改进为动态基线倾角最大化圈绕凸壳串行算法;然后,根据同构化凸壳构造基本定理,利用工作站机群优点,进一步对动态基线倾角最大化圈绕凸壳串行算法施加多域化扩展与并行化改造,并提出效率更高的基于四群四域四向动态基线倾角最大化圈绕的凸壳并行新算法。该凸壳并行新算法的特点是:1)其机群分为4个子机群;2)其数据分布域分为4个子分布域;2)其各子分布域内凸壳顶点的圈绕寻找方向共有4个,即各子分布域均各由自己的逆时针寻找方向。In this paper, the serial algorithm for finding convex hull based on maximum pitch of the base line coiling is improved to be the serial algorithm for finding convex hull based on maximum pitch of the dynamical base line coiling firstly; then, according to the isomorphic fundamental theorem of the convex hull construction and using the advantages of COW （Cluster of workstation）, the serial algorithm for finding convex hull based on maximum pitch of the dynamical base line coiling is extended in multi-domains and is modified in parallel, further a more efficient new parallel algorithm to find a convex hull based on maximum pitch of the dynamical base line coiling with 4-Clusters, 4-Domains and 4-Directions is given. The general characters of the new parallel algorithm are： 1） its COW is combined with four sub-clusters; 2） its domain is divided into four sub-domains; 3） its seeking directions of coiling are four, which the see-king directions of coiling with a maximum pitch of the dynamical base line in every sub-domain is along with one way （anti clockwise direction） of itself separately.

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

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