@article{oai:nitech.repo.nii.ac.jp:00004820,
 author = {Castanho, Dense and Chen, Wei and Wada, Koichi},
 issue = {4},
 journal = {IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences},
 month = {Apr},
 note = {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+42)ε-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., application/pdf},
 pages = {722--732},
 title = {A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points},
 volume = {E83-A},
 year = {2000}
}