Header menu link for other important links
X
Faster output-sensitive parallel convex hulls for d ≤ 3: optimal sublogarithmic algorithms for small outputs
Neelima Gupta,
Published in ACM, New York, NY, United States
1996
Pages: 176 - 185
Abstract
In this paper we focus on the problem of designing very fast parallel algorithms for the convex hull problem in two and three dimensions in the arbitrary CRCW model whose running times are output-size sensitive. We present a fast randomized algorithm for planar hulls that runs in expected time O(log H · log log n) and does optimal O(n log H) work where n and H are the input and output sizes respectively. For log H = Ω(log log n), we can achieve the optimal running time of O(log H) for planar hulls while simultaneously keeping the work optimal. In three dimensions, our algorithm runs in expected time O(log log2 n·log H) with optimal O(n log H) work for all H. Hence, for O(logO(1) n) size outputs, our algorithms in two and three dimensions achieve poly(log log n) running time and optimal O(n log log n) work. The previously known output-sensitive work-optimal algorithms for convex hulls have running times Ω(log n) (expected) and Ω(log3 n) in two and three dimensions respectively. Our algorithms assume no input distribution and the running times hold with high probability. We also describe a very simple O(log n log H) time optimal deterministic algorithm for planar hulls which is an improvement for small outputs. For larger output-sizes, a running time of O(log n log log n)) can be achieved.
About the journal
Published in ACM, New York, NY, United States
Open Access
Impact factor
N/A