{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:46:01Z","timestamp":1770993961033,"version":"3.50.1"},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1996,6]]},"abstract":"<jats:p> We present a parallel algorithm for finding the convex hull of a sorted point set. The algorithm runs in O( log log n) (doubly logarithmic) time using n\/ log log n processors on a Common CRCW PRAM. To break the \u03a9( log n\/ log log n) time barrier required to output the convex hull in a contiguous array, we introduce a novel data structure for representing the convex hull. The algorithm is optimal in two respects: (1) the time-processor product of the algorithm, which is linear, cannot be improved, and (2) the running time, which is doubly logarithmic, cannot be improved even by using a linear number of processors. The algorithm demonstrates the power of the \u201cthe divide-and-conquer doubly logarithmic paradigm\u201d by presenting a non-trivial extension to situations that previously were known to have only slower algorithms. <\/jats:p>","DOI":"10.1142\/s0218195996000162","type":"journal-article","created":{"date-parts":[[2004,9,6]],"date-time":"2004-09-06T07:50:09Z","timestamp":1094457009000},"page":"231-241","source":"Crossref","is-referenced-by-count":9,"title":["A FAST PARALLEL ALGORITHM FOR FINDING THE CONVEX HULL OF A SORTED POINT SET"],"prefix":"10.1142","volume":"06","author":[{"given":"OMER","family":"BERKMAN","sequence":"first","affiliation":[{"name":"Dept. of Computing, King\u2019s College London, The Strand, London WC2R 2LS, England"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BARUCH","family":"SCHIEBER","sequence":"additional","affiliation":[{"name":"IBM Research Division, T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, New York 10598, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"UZI","family":"VISHKIN","sequence":"additional","affiliation":[{"name":"Institute for Advanced Computer Studies (UMIACS), and Dept. of Electrical Engineering, University of Maryland, College Park, Maryland 20742, USA"},{"name":"Dept. of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195996000162","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:31:10Z","timestamp":1565123470000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195996000162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1996,6]]}},"alternative-id":["10.1142\/S0218195996000162"],"URL":"https:\/\/doi.org\/10.1142\/s0218195996000162","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,6]]}}}