An Associative Static and Dynamic Convex Hull Algorithm

Department of Computer Science
Author(s)
Abstract

This paper presents a new static and dynamic recursive parallel algorithm for the convex hull problem. This algorithm is a parallel adaptation of the Graham scan and Quick Hull algorithms. 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. The static algorithm requires O(n) space, O(log n) average case running time, and O(n) worst case running time. If O(log n) ISs are used the, static algorithm should have an average running time of O(log log n).
Format
Article
Identifier(s)
10.1109/IPDPS.2002.1016672
Publication Date
2002
Publication Title
Proceedings of the 16th International Parallel and Distributed Processing Symposium
Publisher
IEEE
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-static-and-dynamic-convex-hull-algorithm
Atwah, M., & Baker, J. (2002). An Associative Static and Dynamic Convex Hull Algorithm (1–). Proceedings of the 16th International Parallel and Distributed Processing Symposium. https://doi.org/10.1109/IPDPS.2002.1016672
Atwah, Maher, and Johnnie Baker. 2002. “An Associative Static and Dynamic Convex Hull Algorithm”. Proceedings of the 16th International Parallel and Distributed Processing Symposium. https://doi.org/10.1109/IPDPS.2002.1016672.
Atwah, Maher, and Johnnie Baker. An Associative Static and Dynamic Convex Hull Algorithm. Proceedings of the 16th International Parallel and Distributed Processing Symposium, 2002, https://doi.org/10.1109/IPDPS.2002.1016672.