The search functionality is under construction.

The search functionality is under construction.

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 in *O*((*n* log *n*)/*p*) computation time with a constant number of communication rounds. The algorithm is also cost optimal for the problem.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1152-1160

- Publication Date
- 2001/05/01

- 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

Naoki OSHIGE, Akihiro FUJIWARA, "Round Optimal Parallel Algorithms for the Convex Hull of Sorted Points" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 5, pp. 1152-1160, May 2001, doi: .

Abstract: 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 in *O*((*n* log *n*)/*p*) computation time with a constant number of communication rounds. The algorithm is also cost optimal for the problem.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_5_1152/_p

Copy

@ARTICLE{e84-a_5_1152,

author={Naoki OSHIGE, Akihiro FUJIWARA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Round Optimal Parallel Algorithms for the Convex Hull of Sorted Points},

year={2001},

volume={E84-A},

number={5},

pages={1152-1160},

abstract={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 in *O*((*n* log *n*)/*p*) computation time with a constant number of communication rounds. The algorithm is also cost optimal for the problem.

keywords={},

doi={},

ISSN={},

month={May},}

Copy

TY - JOUR

TI - Round Optimal Parallel Algorithms for the Convex Hull of Sorted Points

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1152

EP - 1160

AU - Naoki OSHIGE

AU - Akihiro FUJIWARA

PY - 2001

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E84-A

IS - 5

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - May 2001

AB - 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 in *O*((*n* log *n*)/*p*) computation time with a constant number of communication rounds. The algorithm is also cost optimal for the problem.

ER -