Abstract
We investigate the problem of finding the two-dimensional convex hull of a set of points on a coarse-grained parallel computer. Recently Goodrich has devised a parallel sorting algorithm for n items on P processors which achieves an optimal number of communication phases for all ranges of P≤n. Ferreira et al. have recently introduced a deterministic convex hull algorithm with a constant number of communication phases for n and P satisfying n≥P1+ε. Here we obtain a new parallel 2-D convex hull algorithm with an optimal bound on number of communication phases for all values of P≤n while maintaining optimal local computation time.
| Original language | English |
|---|---|
| Pages (from-to) | 596-602 |
| Journal | Proceedings of the International Parallel Processing Symposium, IPPS |
| Publication status | Published - 1997 |
| Externally published | Yes |
| Event | Proceedings of the 1997 11th International Parallel Processing Symposium, IPPS 97 - Geneva, Switz Duration: 1 Apr 1997 → 5 Apr 1997 |
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].Fingerprint
Dive into the research topics of '2-D parallel convex hull algorithm with optimal communication phases'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver