Randomized parallel 3D convex hull algorithm for coarse grained multicomputers

Frank Dehne; Xiaotie Deng; Patrick Dymond; Andreas Fabri; Ashfaq A. Khokhar

Randomized parallel 3D convex hull algorithm for coarse grained multicomputers

Frank Dehne
, Xiaotie Deng
, Patrick Dymond
, Andreas Fabri
, Ashfaq A. Khokhar

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

43 Citations (Scopus)

Abstract

We present a randomized parallel algorithm for constructing the 3D convex hull on a generic p-processor coarse grained multicomputer with arbitrary interconnection network and n/p local memory per processor, where n/p ≥ p^2+ε (for some arbitrarily small ε > 0). For any given set of n points in 3-space, the algorithm computes the 3D convex hull, with high probability, in O(n log n÷p) local computation time and O(1) communication phases with at most O(n÷p) data sent/received by each processor. That is, with high probability, the algorithm computes the 3D convex hull of an arbitrary point set in time O(n log n÷p + Γ_n,p), where Γ_n,p denotes the time complexity of one communication phase. In the terminology of the BSP model, our algorithm requires, with high probability, O(1) supersteps and a synchronization period Θ(n log n÷p). In the LogP model, the execution time of our algorithm is asymptotically optimal for several architectures.

Original language	English
Title of host publication	Annual ACM Symposium on Parallel Algorithms and Architectures
Publisher	ACM
Pages	27-33
Publication status	Published - 1995
Externally published	Yes
Event	Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'95 - Santa Barbara, CA, USA Duration: 17 Jul 1995 → 19 Jul 1995

Conference

Conference	Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'95
City	Santa Barbara, CA, USA
Period	17/07/95 → 19/07/95

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{361156ff7676416b993b18dec6e777e3,

title = "Randomized parallel 3D convex hull algorithm for coarse grained multicomputers",

abstract = "We present a randomized parallel algorithm for constructing the 3D convex hull on a generic p-processor coarse grained multicomputer with arbitrary interconnection network and n/p local memory per processor, where n/p ≥ p2+ε (for some arbitrarily small ε > 0). For any given set of n points in 3-space, the algorithm computes the 3D convex hull, with high probability, in O(n log n÷p) local computation time and O(1) communication phases with at most O(n÷p) data sent/received by each processor. That is, with high probability, the algorithm computes the 3D convex hull of an arbitrary point set in time O(n log n÷p + Γn,p), where Γn,p denotes the time complexity of one communication phase. In the terminology of the BSP model, our algorithm requires, with high probability, O(1) supersteps and a synchronization period Θ(n log n÷p). In the LogP model, the execution time of our algorithm is asymptotically optimal for several architectures.",

author = "Frank Dehne and Xiaotie Deng and Patrick Dymond and Andreas Fabri and Khokhar, \{Ashfaq A.\}",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].; Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'95 ; Conference date: 17-07-1995 Through 19-07-1995",

year = "1995",

language = "English",

pages = "27--33",

booktitle = "Annual ACM Symposium on Parallel Algorithms and Architectures",

publisher = "ACM",

}

TY - GEN

T1 - Randomized parallel 3D convex hull algorithm for coarse grained multicomputers

AU - Dehne, Frank

AU - Deng, Xiaotie

AU - Dymond, Patrick

AU - Fabri, Andreas

AU - Khokhar, Ashfaq A.

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1995

Y1 - 1995

N2 - We present a randomized parallel algorithm for constructing the 3D convex hull on a generic p-processor coarse grained multicomputer with arbitrary interconnection network and n/p local memory per processor, where n/p ≥ p2+ε (for some arbitrarily small ε > 0). For any given set of n points in 3-space, the algorithm computes the 3D convex hull, with high probability, in O(n log n÷p) local computation time and O(1) communication phases with at most O(n÷p) data sent/received by each processor. That is, with high probability, the algorithm computes the 3D convex hull of an arbitrary point set in time O(n log n÷p + Γn,p), where Γn,p denotes the time complexity of one communication phase. In the terminology of the BSP model, our algorithm requires, with high probability, O(1) supersteps and a synchronization period Θ(n log n÷p). In the LogP model, the execution time of our algorithm is asymptotically optimal for several architectures.

AB - We present a randomized parallel algorithm for constructing the 3D convex hull on a generic p-processor coarse grained multicomputer with arbitrary interconnection network and n/p local memory per processor, where n/p ≥ p2+ε (for some arbitrarily small ε > 0). For any given set of n points in 3-space, the algorithm computes the 3D convex hull, with high probability, in O(n log n÷p) local computation time and O(1) communication phases with at most O(n÷p) data sent/received by each processor. That is, with high probability, the algorithm computes the 3D convex hull of an arbitrary point set in time O(n log n÷p + Γn,p), where Γn,p denotes the time complexity of one communication phase. In the terminology of the BSP model, our algorithm requires, with high probability, O(1) supersteps and a synchronization period Θ(n log n÷p). In the LogP model, the execution time of our algorithm is asymptotically optimal for several architectures.

UR - http://www.scopus.com/inward/record.url?scp=0029182718&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0029182718&origin=recordpage

M3 - RGC 32 - Refereed conference paper (with host publication)

SP - 27

EP - 33

BT - Annual ACM Symposium on Parallel Algorithms and Architectures

PB - ACM

T2 - Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'95

Y2 - 17 July 1995 through 19 July 1995

ER -

Randomized parallel 3D convex hull algorithm for coarse grained multicomputers

Abstract

Conference

Bibliographical note

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this