Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima
✍ Scribed by Neelima Gupta; Sandeep Sen
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 263 KB
- Volume
- 63
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper we focus on the problem of designing very fast parallel algorithms for the convex hull and the vector maxima problems in three dimensions that are output-size sensitive. Our algorithms achieve Oðlog log 2 n log hÞ parallel time and optimal Oðn log hÞ work with high probability in the CRCW PRAM where n and h are the input and output size, respectively. These bounds are independent of the input distribution and are faster than the previously known algorithms. We also present an optimal speed-up (with respect to the input size only) sublogarithmic time algorithm that uses superlinear number of processors for vector maxima in three dimensions.