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

• 作者: 周世泉 许胤龙 赵建勇 陈国良
• 来源期刊: 计算机科学
• 关键词: 凸壳 并行算法 可重构流水线总线
• 年，卷（期）: 2004,（9）
• 所属期刊栏目: 软件工程
• 页码范围: 144-148
• 页数: 5页
• 字数: 7264字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2004.09.040

摘要

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