基于动态基线倾角与基线距离最大化的凸壳并行新算法  

A New Parallel Algorithm for Finding Convex Hull Based on Maximum Pitch and Distance of the Dynamical Base Line

作　　者：周启海[1] 黄涛[1] 林珣[1] 李忠俊[1] 

机构地区：[1]西南财经大学信息技术应用研究所

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

摘　　要：本文根据同构化凸壳构造基本定理,整合了"动态基线倾角最大化"凸壳并行算法思想与"动态基线距离最大化圈绕凸壳"凸壳串行算法思想的各自优点,并对后者施以多域化扩展与并行化改造,从而提出效率更高的基于动态基线倾角与动态基线距离最大化的凸壳并行新算法。该凸壳并行新算法的特点是:1)其机群分为4个子机群,其数据分布域分为4个子分布域,其各子分布域内凸壳顶点的圈绕寻找方向共有4个,即各子分布域均各由自己的逆时针寻找方向;2)对各子分布域的当前动态基线,均并行地找出其当前动态基线倾角最大点与当前动态基线距离最大点,并作为其各子分布域内凸壳的新顶点。In this paper, the advantages of both ＂the parallel algorithm thinking for finding convex hull based on maximum pitch of the dynamical base line＂ and ＂the serial algorithm thinking for finding convex hull based on maximum distance of the dynamical base line＂ are integrated, and the later 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 and distance of the dynamical base line is given. The general characters of this new parallel algorithm are： 1） its COW is combined with four subclusters, its domain is divided into four sub-domains, its seeking directions of coiling are four, which the seeking 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; 2） parallel find out the maximum pitch and the maximum distance for their current dynamical base line in every sub-domain separately.

关 键 词：同构化 机群 凸壳 并行算法 动态基线倾角 动态基线距离 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论] TP301.6[自动化与计算机技术—计算机科学与技术]