Round Optimal Parallel Algorithms for the Convex Hull of Sorted Points (Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
In this paper, we present deterministic parallel algorithms for the convex hull of sorted points and their application to a related problem. The algorithms are proposed for the coarse grained multicomputer (CGM) model. We first propose a cost optimal parallel algorithm for computing the problem with a constant number of communication rounds for n/p≥p^2, where n is the size of an input and p is the number of processors. Next we propose a cost optimal algorithm, which is more complicated, for n/p≥p^ε, where 0<ε<2. From the above two results, we can compute the convex hull of sorted points with O(n/p) computation time and a constant number of communication rounds for n/p≥p^ε where ε>0. Finally we show an application of our convex hull algorithms. We solve the convex layers for d lines O(<n log n>/p) computation time with a constant number of communication rounds. The algorithm is also cost optimal for the problem.
社団法人電子情報通信学会の論文
2001-05-01