{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:44:43Z","timestamp":1775069083291,"version":"3.50.1"},"reference-count":35,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1994,2,1]],"date-time":"1994-02-01T00:00:00Z","timestamp":760060800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":7106,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[1994,2]]},"DOI":"10.1016\/s0022-0000(05)80023-6","type":"journal-article","created":{"date-parts":[[2005,8,20]],"date-time":"2005-08-20T07:18:35Z","timestamp":1124522315000},"page":"90-115","source":"Crossref","is-referenced-by-count":14,"title":["Parallel solutions to geometric problems in the scan model of computation"],"prefix":"10.1016","volume":"48","author":[{"given":"Guy E.","family":"Blelloch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James J.","family":"Little","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(05)80023-6_bib1","series-title":"Proceedings, Symposium on Foundations of Computer Science","first-page":"468","article-title":"Parallel computational geometry","author":"Aggarwal","year":"1985"},{"key":"10.1016\/S0022-0000(05)80023-6_bib2","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/0020-0190(79)90156-X","article-title":"Two remarks on a convex hull algorithm","volume":"8","author":"Akl","year":"1979","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0022-0000(05)80023-6_bib3","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1137\/0218035","article-title":"Cascading divide-and-conquer: A technique for designing parallel algorithms","volume":"18","author":"Atallah","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(05)80023-6_bib4","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\/S0022-0000(05)80023-6_bib5","series-title":"Proceedings, ACM Symposium on Theory of Computing","first-page":"216","article-title":"Efficient plane sweeping in parallel","author":"Atallah","year":"1986"},{"key":"10.1016\/S0022-0000(05)80023-6_bib6","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional binary search trees used for associative searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Commun. ACM"},{"key":"10.1016\/S0022-0000(05)80023-6_bib7","series-title":"Proceedings, ACM Symposium on Theory of Computing","first-page":"220","article-title":"Divide-and-conquer in multidimensional space","author":"Bentley","year":"1976"},{"key":"10.1016\/S0022-0000(05)80023-6_bib8","doi-asserted-by":"crossref","first-page":"1526","DOI":"10.1109\/12.42122","article-title":"Scans as primitive parallel operations","volume":"C-38","author":"Blelloch","year":"1989","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0022-0000(05)80023-6_bib9","series-title":"Vector Models for Data-Parallel Computing","author":"Blelloch","year":"1990"},{"key":"10.1016\/S0022-0000(05)80023-6_bib10","series-title":"Proceedings, Frontiers of Massively Parallel Computation","article-title":"VCODE: A data-parallel intermediate language","author":"Blelloch","year":"1990"},{"key":"10.1016\/S0022-0000(05)80023-6_bib11","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0206054","article-title":"On relating time and space to size and depth","volume":"6","author":"Borodin","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(05)80023-6_bib12","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","article-title":"The parallel evaluation of general arithmetic expressions","volume":"21","author":"Brent","year":"1974","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0022-0000(05)80023-6_bib13","series-title":"Proceedings, Supercomputing '90","article-title":"Scan primitives for vector computers","author":"Chatterjee","year":"1990"},{"key":"10.1016\/S0022-0000(05)80023-6_bib14","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","article-title":"Parallel merge sort","volume":"17","author":"Cole","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(05)80023-6_bib15","series-title":"Proceedings, Fourth Annual Symposium on Computational Geometry","article-title":"Optimal parallel algorithms for point-set and polygon problems","author":"Cole","year":"1988"},{"key":"10.1016\/S0022-0000(05)80023-6_bib16","series-title":"Proceedings, ACM Symposium on Theory of Computing","first-page":"206","article-title":"Deterministic coin tossing and accelerating cascades: Micro and macro techniques for designing parallel algorithms","author":"Cole","year":"1986"},{"key":"10.1016\/S0022-0000(05)80023-6_bib17","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","article-title":"A taxonomy of problems with fast parallel algorithms","volume":"64","author":"Cook","year":"1985","journal-title":"Inform. and Control"},{"key":"10.1016\/S0022-0000(05)80023-6_bib18","series-title":"Proceedings, ACM Symposium on Theory of Computing","first-page":"114","article-title":"Parallelism in random access machines","author":"Fortune","year":"1978"},{"key":"10.1016\/S0022-0000(05)80023-6_bib19","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1145\/356625.356627","article-title":"Computer processing of line-drawing images","volume":"6","author":"Freeman","year":"1974","journal-title":"Comput. Surveys"},{"key":"10.1016\/S0022-0000(05)80023-6_bib20","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/355744.355745","article-title":"An algorithm for finding best matches in logarithmic expected time","volume":"3","author":"Friedman","year":"1977","journal-title":"ACM Trans. Math. Software"},{"key":"10.1016\/S0022-0000(05)80023-6_bib21","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","article-title":"A universal interconnection pattern for parallel computers","volume":"29","author":"Goldschlager","year":"1982","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0022-0000(05)80023-6_bib22","series-title":"Topology","author":"Hocking","year":"1961"},{"key":"10.1016\/S0022-0000(05)80023-6_bib23","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0020-0190(73)90020-3","article-title":"On the identification of the convex hull on a finite set of points in the plane","volume":"2","author":"Jarvis","year":"1973","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0022-0000(05)80023-6_bib24","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","article-title":"Parallel prefix computation","volume":"27","author":"Ladner","year":"1980","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0022-0000(05)80023-6_bib25","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."},{"key":"10.1016\/S0022-0000(05)80023-6_bib26","series-title":"Principles of Interactive Computer Graphics","author":"Newman","year":"1979"},{"key":"10.1016\/S0022-0000(05)80023-6_bib27","article-title":"Efficient algorithms with neural network behavior","volume":"1","author":"Omohundro","year":"1987","journal-title":"Complex Systems"},{"key":"10.1016\/S0022-0000(05)80023-6_bib28","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","article-title":"Maintenance of configurations in the plane","volume":"23","author":"Overmars","year":"1981","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(05)80023-6_bib29","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/S0022-0000(76)80037-2","article-title":"A characterization of the power of vector machines","volume":"12","author":"Pratt","year":"1976","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(05)80023-6_bib30","series-title":"Computational Geometry\u2014An Introduction","author":"Preparata","year":"1985"},{"key":"10.1016\/S0022-0000(05)80023-6_bib31","series-title":"Proceedings, International Conference on Parallel Processing","first-page":"270","article-title":"Optimal randomized parallel algorithms for computational geometry","author":"Reif","year":"1987"},{"key":"10.1016\/S0022-0000(05)80023-6_bib32","article-title":"*Render: A Data Parallel Approach to Polygon Rendering","author":"Salem","year":"1988"},{"key":"10.1016\/S0022-0000(05)80023-6_bib33","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1145\/357114.357116","article-title":"Ultracomputers","volume":"2","author":"Schwartz","year":"1980","journal-title":"ACM Trans. Programming Lang. Systems"},{"key":"10.1016\/S0022-0000(05)80023-6_bib34","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","article-title":"Finding the maximum, merging and sorting in a parallel computation model","volume":"2","author":"Shiloach","year":"1981","journal-title":"J. Algorithms"},{"key":"10.1016\/S0022-0000(05)80023-6_bib35","series-title":"Proceedings, ACM Symposium on Theory of Computing","first-page":"196","article-title":"Universal circuits (preliminary report)","author":"Valiant","year":"1976"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000005800236?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000005800236?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,22]],"date-time":"2019-01-22T17:27:45Z","timestamp":1548178065000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000005800236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,2]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,2]]}},"alternative-id":["S0022000005800236"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(05)80023-6","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[1994,2]]}}}