Header menu link for other important links
Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima
N. Gupta,
Published in Academic Press Inc.
Volume: 63
Issue: 4
Pages: 488 - 500
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 0(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. © 2003 Elsevier Science (USA). All rights reserved.
About the journal
Published in Academic Press Inc.
Open Access
Impact factor