|
EPrints@IIT Delhi >
Faculty Research Publicatons >
Computer Science and Engineering >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/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 in... |
| URI: | http://eprint.iitd.ac.in/dspace/handle/2074/360 |
| Appears in Collections: | Computer Science and Engineering
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| guptaopt97.pdf | | 426Kb | Adobe PDF | View/Open |
|
Show full item record
All items in DSpace are protected by copyright, with all rights reserved.
|
