Optimal, output-sensitive algorithms for constructing planar hulls in parallel

Gupta, Neelima ; Sen, Sandeep (1997) Optimal, output-sensitive algorithms for constructing planar hulls in parallel Computational Geometry, 8 (3). pp. 151-166. ISSN 0925-7721

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1016/S0925-7721(97)00009-6

Abstract

In this paper we focus on the problem of designing very fast parallel algorithms for the planar convex hull problem that achieve the optimal O(nlogH) work-bound for input size n and output size H. Our algorithms are designed for the arbitrary CRCW PRAM model. We first describe a very simple O(lognlogH) time optimal deterministic algorithm for the planar hulls which is an improvement over the previously known Ω(log2n) time algorithm for small outputs. For larger values of H, we can achieve a running time of O(log n log log n) steps with optimal work. We also present a fast randomized algorithm that runs in expected time O(logH·log log n) and does optimal O(n logH) work. For logH=Ω(log log n), we can achieve the optimal running time of O(logH) while simultaneously keeping the work optimal. When logH is o(logn), our results improve upon the previously best known Θ(logn) expected time randomized algorithm of Ghouse and Goodrich. The randomized algorithms do not assume any input distribution and the running times hold with high probability.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Parallel Algorithm; Computational Geometry; Convex Hull; Randomized Algorithm
ID Code:53424
Deposited On:08 Aug 2011 12:09
Last Modified:08 Aug 2011 12:09

Repository Staff Only: item control page