@inproceedings{957ca88e8c7d47d792d116ebfa015d89,

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

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-boundfor 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 boundfor H = Ω(log n). We present a fast randomized algorithm that runs in expectedtime O(logH ・ log log n) with high probability andd oes O(n logH) work. For logH = Ω(log log n), we can achieve the running time of O(logH) while simultaneously keeping the work optimal. We also present a fast randomized algorithm that runs in ˜O(log n/ log k) time with nk processors, k > logΩ(1) n. The algorithms do not assume any input distribution andthe running times holdwith high probability.",

author = "Neelima Gupta and Sumit Chopra and Sandeep Sen",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 21st Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS 2001 ; Conference date: 13-12-2001 Through 15-12-2001",

year = "2001",

doi = "10.1007/3-540-45294-x_16",

language = "English (US)",

isbn = "3540430024",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "183--194",

editor = "Ramesh Hariharan and V. Vinay and Madhavan Mukund",

booktitle = "FST TCS 2001",

}