
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points
Carla Denise CASTANHO Wei CHEN Koichi WADA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E83A
No.4
pp.722732 Publication Date: 2000/04/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: computational geometry, convexity, strongly convex superhull, parallel algorithm, divideandconquer,
Full Text: PDF(670.8KB)>>
Summary:
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 EREWPRAM 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.

