{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:04:28Z","timestamp":1763467468547,"version":"3.44.0"},"reference-count":29,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[1998,5,19]],"date-time":"1998-05-19T00:00:00Z","timestamp":895536000000},"content-version":"vor","delay-in-days":444,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Computational Geometry"],"published-print":{"date-parts":[[1997,3]]},"DOI":"10.1016\/0925-7721(95)00036-4","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T08:08:03Z","timestamp":1027584483000},"page":"219-235","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":4,"title":["Fast randomized parallel methods for planar convex hull construction"],"prefix":"10.1016","volume":"7","author":[{"given":"Mujtaba R.","family":"Ghouse","sequence":"first","affiliation":[]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0925-7721(95)00036-4_BIB1","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/BF01762120","article-title":"Parallel computational geometry","volume":"3","author":"Aggarwal","year":"1988","journal-title":"Algorithmica"},{"key":"10.1016\/0925-7721(95)00036-4_BIB2","series-title":"Proc. 31st IEEE Symp. Found. Comput. Sci.","first-page":"574","article-title":"Parallel linear programming in fixed dimension almost surely in constant time","author":"Alon","year":"1990"},{"key":"10.1016\/0925-7721(95)00036-4_BIB3","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1016\/0743-7315(86)90011-0","article-title":"Efficient parallel solutions to some geometric problems","volume":"3","author":"Atallah","year":"1986","journal-title":"J. Parallel Distrib. Comput."},{"key":"10.1016\/0925-7721(95)00036-4_BIB4","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1007\/BF01762130","article-title":"Parallel algorithms for some functions of two convex polygons","volume":"3","author":"Atallah","year":"1988","journal-title":"Algorithmica"},{"key":"10.1016\/0925-7721(95)00036-4_BIB5","unstructured":"O. Berkman, B. Schieber and U. Vishkin, A fast parallel algorithm for finding the convex hull of a sorted point set, Internat. J. Comput. Geom. Appl., to appear."},{"key":"10.1016\/0925-7721(95)00036-4_BIB6","series-title":"Technical Report","article-title":"Derandomizing an output-sensitive convex hull algorithm in three dimensions","author":"Chazelle","year":"1992"},{"issue":"1","key":"10.1016\/0925-7721(95)00036-4_BIB7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1109\/71.363412","article-title":"Efficient geometric algorithms on the EREW PRAM","volume":"6","author":"Chen","year":"1995","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"10.1016\/0925-7721(95)00036-4_BIB8","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","article-title":"A measure of asymptotic efficiency for tests of a hypothesis based on the sum of the observations","volume":"23","author":"Chernoff","year":"1952","journal-title":"Annals of Math. Stat."},{"article-title":"Parallel algorithms for geometric problems","year":"1980","author":"Chow","key":"10.1016\/0925-7721(95)00036-4_BIB9"},{"key":"10.1016\/0925-7721(95)00036-4_BIB10","series-title":"Proc. 19th Allerton Conf. Commun. Control Comput.","first-page":"214","article-title":"A parallel algorithm for determining convex hulls of sets of points in two dimensions","author":"Chow","year":"1981"},{"key":"10.1016\/0925-7721(95)00036-4_BIB11","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0020-0190(90)90026-T","article-title":"An optimal parallel algorithm for linear programming in the plane","volume":"35","author":"Deng","year":"1990","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0925-7721(95)00036-4_BIB12","article-title":"Algorithms in Combinatorial Geometry","volume":"Vol. 10","author":"Edelsbrunner","year":"1987"},{"key":"10.1016\/0925-7721(95)00036-4_BIB13","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1146\/annurev.cs.03.060188.001313","article-title":"Parallel algorithmic techniques for combinatorial computation","volume":"3","author":"Eppstein","year":"1988","journal-title":"Annual Review of Computer Science"},{"key":"10.1016\/0925-7721(95)00036-4_BIB14","series-title":"Proc. 3rd ACM Symp. Parallel Algorithms Architect","first-page":"192","article-title":"In-place techniques for parallel convex hull algorithms","author":"Ghouse","year":"1991"},{"key":"10.1016\/0925-7721(95)00036-4_BIB15","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/0020-0190(87)90002-0","article-title":"Finding the convex hull of a sorted point set in parallel","volume":"26","author":"Goodrich","year":"1987","journal-title":"Inform. Process. Lett."},{"issue":"5","key":"10.1016\/0925-7721(95)00036-4_BIB16","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0925-7721(93)90023-Y","article-title":"Constructing the convex hull of a partially sorted set of points","volume":"2","author":"Goodrich","year":"1993","journal-title":"Computational Geometry: Theory and Applications"},{"key":"10.1016\/0925-7721(95)00036-4_BIB17","series-title":"Proc. 5th ACM-SIAM Symp. on Discrete Algorithms","first-page":"241","article-title":"Optimal parallel approximation for prefix sums and integer sorting","author":"Goodrich","year":"1994"},{"key":"10.1016\/0925-7721(95)00036-4_BIB18","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","article-title":"An efficient algorithm for determining the convex hull of a finite planar set","volume":"1","author":"Graham","year":"1972","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0925-7721(95)00036-4_BIB19","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0020-0190(89)90138-5","article-title":"Optimal merging and sorting on the erew pram","volume":"33","author":"Hagerup","year":"1989","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0925-7721(95)00036-4_BIB20","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","article-title":"A guided tour of Chernoff bounds","volume":"33","author":"Hagerup","year":"1990","journal-title":"Inform. Process. Lett."},{"year":"1992","series-title":"An Introduction to Parallel Algorithms","author":"J\u00e1j\u00e1","key":"10.1016\/0925-7721(95)00036-4_BIB21"},{"key":"10.1016\/0925-7721(95)00036-4_BIB22","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","article-title":"The ultimate planar convex hull algorithm?","volume":"15","author":"Kirkpatrick","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0925-7721(95)00036-4_BIB23","series-title":"Proc. 23rd ACM Symp. Theory Comput.","first-page":"307","article-title":"Converting high probability into nearly-constant time\u2014with applications to parallel hashing","author":"Matias","year":"1991"},{"issue":"12","key":"10.1016\/0925-7721(95)00036-4_BIB24","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1109\/12.9737","article-title":"Efficient parallel convex hull algorithms","volume":"37","author":"Miller","year":"1988","journal-title":"IEEE Trans. Comput."},{"year":"1994","series-title":"Computational Geometry in C","author":"O'Rourke","key":"10.1016\/0925-7721(95)00036-4_BIB25"},{"year":"1985","series-title":"Computational Geometry: An Introduction","author":"Preparata","key":"10.1016\/0925-7721(95)00036-4_BIB26"},{"key":"10.1016\/0925-7721(95)00036-4_BIB27","series-title":"Proc. 17th International Colloquium on Automata","first-page":"744","article-title":"The parallel simplicity of compaction and chaining","volume":"443","author":"Ragde","year":"1990"},{"key":"10.1016\/0925-7721(95)00036-4_BIB28","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0020-0190(90)90140-S","article-title":"Finding an approximate median with high probability in constant parallel time","volume":"34","author":"Sen","year":"1990","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0925-7721(95)00036-4_BIB29","doi-asserted-by":"crossref","first-page":"780","DOI":"10.1145\/322276.322289","article-title":"A lower bound to finding convex hulls","volume":"28","author":"Yao","year":"1981","journal-title":"J. ACM"}],"container-title":["Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0925772195000364?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0925772195000364?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T16:39:57Z","timestamp":1757522397000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0925772195000364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["0925772195000364"],"URL":"https:\/\/doi.org\/10.1016\/0925-7721(95)00036-4","relation":{},"ISSN":["0925-7721"],"issn-type":[{"type":"print","value":"0925-7721"}],"subject":[],"published":{"date-parts":[[1997,3]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Fast randomized parallel methods for planar convex hull construction","name":"articletitle","label":"Article Title"},{"value":"Computational Geometry","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/0925-7721(95)00036-4","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1997 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}