一维可重构流水线总线并行机上平面点集的凸壳算法  

A Convex Hull Algorithm for a Planer Point Set on LARPBS

作　　者：周世泉[1] 许胤龙[1] 陈国良[1] 赵建勇[1] 

机构地区：[1]中国科学技术大学计算机系国家高性能计算中心,合肥230027

出　　处：《计算机科学》2004年第9期144-148,共5页Computer Science

基　　金：本文工作受国家863项目"SMP机群体系结构上并行算法的研究与实现"(No:2001AA111041)的资助

摘　　要：确定平面点集的凸壳是计算几何中的一个基本问题。一维可重构流水线总线并行机是近年提出的一种采用光连接的并行计算模型。本文在规模为n的可重构流水线总线并行机上提出了一个计算n个平面点的凸壳算法,当n个点按横坐标递增的顺序存储时,该算法的时间复杂度为O(logn)。Computing the convex hull of a given set of planar points is one of the most extensively investigated topics in computational geometry. A linear array with a reconfigurable pipelined bus system (LARPBS) is one of the recently proposed parallel architectures based on optical buses. This paper presents a parallel algorithm for convex hull computation of a given set of n planar points on LARPBS with n processors. In the case of the given n points being stored in LARPBS according to the alphabet order of their coordinates, one per processor, the algorithm runs in time O(logn).

关 键 词：凸壳 总线 可重构 并行机 流水线 算法 平面点集 一维 计算几何 坐标 

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