EPrints@IIT Delhi >
Faculty Research Publicatons  >
Computer Science and Engineering >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/360

Title: Optimal, output-sensitive algorithms for constructing planar hulls in parallel
Authors: Gupta, Neelima
Sen, Sandeep
Keywords: Parallel algorithm
Computational geometry
Convex hull
Randomized algorithm
Issue Date: 1997
Citation: Computational geometry, 8, 151-166
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(n log H) 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(log n log H) time optimal deterministic algorithm for the planar hulls which is an improvement over the previously known ~(log 2 n) 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 ©(log H- log log n) and does optimal O(nlogH) work. For logH = ~2(log log n), we can achieve the optimal running time of O(log H) while simultaneously keeping the work optimal. When log H is o(log n), our results improve upon the previously best known o(log n) 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.
URI: http://eprint.iitd.ac.in/dspace/handle/2074/360
Appears in Collections:Computer Science and Engineering

Files in This Item:

File Description SizeFormat
guptaopt97.pdf426.33 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback