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. © Springer-Verlag Berlin Heidelberg 2001.