A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points(Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
Let S be a set of n points in the plane and CH(S) be the convex hull of S. We consider the problem of constructing an approximate convex hull which contains CH(S)with strong convexity. An ε-convex δ-superhull of S is a convex polygon P satisfying the following conditions: (1)P has at most O(n) vertices, (2) P contains S, (3) no vertex of P lies farther than δ outside CH(S), and (4)P remains convex even if its vertices are perturbed by as much as ε. The parameters ε and δ represent the strength of convexity of P and the degree of approximation of P to CH(S), respectively. This paper presents the first parallel method for the problem. We show that an ε-convex (8+4√<2>)ε-superhull of S can be constructed in O(log n) time using O(n) processors, or in O(log n) time using O(n/log n) processors if S is sorted, in the EREW-PRAM model. We implement the algorithm and find that the average performance is even much better: the results are more strongly convex and much more approximate to CH(S) than the theoretical analysis shows.
社団法人電子情報通信学会の論文
2000-04-25