A sublogarithmic convex hull algorithm
A sublogarithmic convex hull algorithm
复制标题
次对数凸包算法
DOI：
10.1007/bf01931655
复制
发表时间：
1990
影响因子：
1.5
通讯作者：
O. Petersson
中科院分区：
文献类型：
--
作者：
Per;J. Katajainen;C. Levcopoulos;O. Petersson
本文提出了一种求平面上有序点集的凸船体的并行算法。我们的算法运行在O（logn/loglogn）时间使用O（nloglogn/logn）处理器在公共crcwpram计算模型，这是时间和成本最优。该算法是基于n1/3分而治之，并使用一个简单的指针为基础的数据结构。
We present a parallel algorithm for finding the convex hull of a sorted set of points in the plane. Our algorithm runs inO(logn/log logn) time usingO(n log logn/logn) processors in theCommon crcw pram computational model, which is shown to be time and cost optimal. The algorithm is based onn1/3 divide-and-conquer and uses a simple pointer-based data structure.