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

摘要：

确定平面点集的凸壳是计算几何中的一个基本问题.一维可重构流水线总线并行机是近年提出的一种采用光连接的并行计算模型.本文在规模为n的可重构流水线总线并行机上提出了一个计算n个平面点的凸壳算法,当n个点按横坐标递增的顺序存储时,该算法的时间复杂度为O(1ogn).

关键词：凸壳、并行算法、可重构流水线总线

所属期刊栏目：31

分类号：TP3;TP2

资助基金：国家高技术研究发展计划863计划2001AA111041

在线出版日期：2004-11-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：144-148