An Associative Implementation of Graham's Convex Hull Algorithm

Department of Computer Science
Author(s)
Abstract

This paper presents a new parallel algorithm for the convex hull problem. This algorithm is a parallel adaptation of the Graham Scan Algorithm. The computational model selected for this algorithm is the associative computing model (ASC) which supports massive parallelism through the use of data parallelism and constant time associative search and maximum functions. Also, ASC can be supported on existing SIMD computers. This algorithm requires O(n) space, O(n log n) average cost, and O(n2) worst case cost. The algorithm has been implemented and tested on random data.
Format
Article
Publication Date
1996-10
Publication Title
Proceedings of the Seventh IASTED International Conference on Parallel and Distributed Computing and Systems
First Page
273
Last Page
276
Keywords
Subject
Rights
http://rightsstatements.org/vocab/InC/1.0/
Community
Department of Computer Science
Permalink https://oaks.kent.edu/kenneth-e-batcher-collection/associative-implementation-grahams-convex-hull-algorithm
Atwah, M., & Baker, J. (1996). An Associative Implementation of Graham’s Convex Hull Algorithm (1–). Proceedings of the Seventh IASTED International Conference on Parallel and Distributed Computing and Systems. https://oaks.kent.edu/node/17417
Atwah, Maher, and Johnnie Baker. 1996. “An Associative Implementation of Graham’s Convex Hull Algorithm”. Proceedings of the Seventh IASTED International Conference on Parallel and Distributed Computing and Systems. https://oaks.kent.edu/node/17417.
Atwah, Maher, and Johnnie Baker. An Associative Implementation of Graham’s Convex Hull Algorithm. Proceedings of the Seventh IASTED International Conference on Parallel and Distributed Computing and Systems, Oct. 1996, https://oaks.kent.edu/node/17417.