Finding the convex hull of a sorted point set in parallel |
| |
| Affiliation: | 1. School of Computer Science and Engineering, State Key Laboratory of Software Development Environment, Jiangxi Research Institute, Beihang University, China;2. Institute of Semiconductors Chinese Adacamy of Sciences Laboratory of Artificial Neural Networks and High-speed Circuits, Beijing, China;3. School of Information and Communication Technology, Griffith University, Nathan, Queensland 4111, Australia;4. Department of Computer Science, University of York, York, UK |
| |
| Abstract: | We present a parallel algorithm for finding the convex hull of a sorted planar point set. Our algorithm runs in O(log n) time using O(n/log n) processors in the CREW PRAM computational model, which is optimal. One of the techniques we use to achieve these optimal bounds is the use of a parallel data structure which we call the hull tree. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
