An Associative Implementation of Classical Convex Hull Algorithm

Department of Computer Science
Author(s)
Abstract

This paper will present the implementation and comparison of new parallel algorithms for the convex hull problem. These algorithms are a parallel adaptation of the Jarvis March and the Quickhull algorithms. The computational model selected for these algorithms is the associative computing model (ASC) and the multiple associative computing model (MASC). Both models support massive parallelism through the use of data parallelism and constant time associative search and maximum functions. Also, ASC can be supported on many SIMD computers. These algorithms requires O(n) space, O(log n) (i.e., O(log2 n)) average running time, and O(n) worst case running time. These algorithms have been compared using random data.
Format
Article
Publication Date
1996-10
Publication Title
Proceedings of the Eighth IASTED International Conference on Parallel and Distributed Computing Systems
First Page
435
Last Page
438
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-classical-convex-hull-algorithm
Atwah, M., Baker, J., & Akl, S. (1996). An Associative Implementation of Classical Convex Hull Algorithm (1–). Proceedings of the Eighth IASTED International Conference on Parallel and Distributed Computing Systems. https://oaks.kent.edu/node/17416
Atwah, Maher, Johnnie Baker, and Selim Akl. 1996. “An Associative Implementation of Classical Convex Hull Algorithm”. Proceedings of the Eighth IASTED International Conference on Parallel and Distributed Computing Systems. https://oaks.kent.edu/node/17416.
Atwah, Maher, et al. An Associative Implementation of Classical Convex Hull Algorithm. Proceedings of the Eighth IASTED International Conference on Parallel and Distributed Computing Systems, Oct. 1996, https://oaks.kent.edu/node/17416.