The search functionality is under construction.

The search functionality is under construction.

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*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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.722-732

- Publication Date
- 2000/04/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Carla Denise CASTANHO, Wei CHEN, Koichi WADA, "A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 4, pp. 722-732, April 2000, doi: .

Abstract: 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*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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_4_722/_p

Copy

@ARTICLE{e83-a_4_722,

author={Carla Denise CASTANHO, Wei CHEN, Koichi WADA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points},

year={2000},

volume={E83-A},

number={4},

pages={722-732},

abstract={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*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.

keywords={},

doi={},

ISSN={},

month={April},}

Copy

TY - JOUR

TI - A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 722

EP - 732

AU - Carla Denise CASTANHO

AU - Wei CHEN

AU - Koichi WADA

PY - 2000

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E83-A

IS - 4

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - April 2000

AB - 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*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.

ER -