Optimal, output-sensitive algorithms for constructing upper envelope of line segments in parallel

Gupta, Neelima ; Chopra, Sumit ; Sen, Sandeep (2001) Optimal, output-sensitive algorithms for constructing upper envelope of line segments in parallel Lecture Notes in Computer Science, 2245 . pp. 183-194. ISSN 0302-9743

[img]
Preview
PDF - Author Version
216kB

Official URL: http://www.springerlink.com/content/b06q0d34ag09b8...

Related URL: http://dx.doi.org/10.1007/3-540-45294-X_16

Abstract

In this paper we focus on the problem of designing very fast parallel algorithms for constructing the upper envelope of straight-line segments that achieve the O(n logH) work-bound for input size n and output size H. Our algorithms are designed for the arbitrary CRCW PRAM model. We first describe an O(log n.(logH + log log n)) time deterministic algorithm for the problem, that achieves O(n logH) work bound for H = Ω(log n). We present a fast randomized algorithm that runs in expected time O(logH.log n) with high probability and does O(n logH) work. For log H = Ω(log log n), we can achieve the running time of O(log H) while simultaneously keeping the work optimal. We also present a fast randomized algorithm that runs in Õ(log n/ log k) time with nk processors, k > logΩ(1) n. The 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 Springer.
ID Code:90085
Deposited On:04 May 2012 14:30
Last Modified:19 May 2016 04:25

Repository Staff Only: item control page