{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T18:44:20Z","timestamp":1772822660950,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1995,8,1]],"date-time":"1995-08-01T00:00:00Z","timestamp":807235200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,8]]},"DOI":"10.1007\/bf01293667","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T22:06:22Z","timestamp":1111701982000},"page":"169-182","source":"Crossref","is-referenced-by-count":6,"title":["A time-optimal parallel algorithm for three-dimensional convex hulls"],"prefix":"10.1007","volume":"14","author":[{"given":"N. M.","family":"Amato","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F. P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: an Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos.Computational Geometry: an Introduction Springer-Verlag, New York, 1985."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set.Inform. Process. Lett., 1:132?133, 1972.","journal-title":"Inform. Process. Lett."},{"issue":"5","key":"CR3","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0020-0190(79)90072-3","volume":"9","author":"A. M. Andrew","year":"1979","unstructured":"A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions.Inform. Process. Lett., 9(5):216?219, 1979.","journal-title":"Inform. Process. Lett."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/359423.359430","volume":"20","author":"F. P. Preparata","year":"1977","unstructured":"F. P. Preparata and S. J. Hong. Convex hulls of finite sets of points in two and three dimensions.Comm. ACM, 20:87?93, 1977.","journal-title":"Comm. ACM"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1016\/0743-7315(86)90011-0","volume":"3","author":"M. J. Atallah","year":"1986","unstructured":"M. J. Atallah and M. T. Goodrich. Efficient parallel solutions to some geometric problems.J. Parallel Distrib. Comput., 3:492?507, 1986.","journal-title":"J. Parallel Distrib. Comput."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/BF01762120","volume":"3","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal, B. Chazelle, L. Guibas, C. \u00d3'D\u00fanlaing, and C. Yap. Parallel computational geometry.Algorithmica, 3:293?327, 1988.","journal-title":"Algorithmica"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1007\/BF01762130","volume":"3","author":"M. J. Atallah","year":"1988","unstructured":"M. J. Atallah and M. T. Goodrich. Parallel algorithms for some functions of two convex polygons.Algorithmica, 3:535?548, 1988.","journal-title":"Algorithmica"},{"issue":"12","key":"CR8","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1109\/12.9737","volume":"37","author":"R. Miller","year":"1988","unstructured":"R. Miller and Q. F. Stout. Efficient parallel convex hull algorithms.IEEE Trans. Comput., 37(12):1605?1618, 1988.","journal-title":"IEEE Trans. Comput."},{"key":"CR9","unstructured":"D. Z. Chen. Efficient geometric algorithms in the EREW-PRAM.Proc. 28th Allerton Conf. on Communications, Control, and Computing, pp. 818?827, 1990."},{"key":"CR10","volume-title":"Ph.D. thesis","author":"A. L. Chow","year":"1980","unstructured":"A. L. Chow. Parallel Algorithms for Geometric Problems. Ph.D. thesis, Department of Computer Science, University of Illinois, Urbana, IL, 1980."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0022-0000(89)90042-1","volume":"39","author":"N. Dadoun","year":"1989","unstructured":"N. Dadoun and D. G. Kirkpatrick. Parallel construction of subdivision hierarchies.J. Comput. System Sci., 39:153?165, 1989.","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"CR12","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1142\/S021819599200010X","volume":"2","author":"N. M. Amato","year":"1992","unstructured":"N. M. Amato and F. P. Preparata. The parallel 3D convex hull problem revisited.Internat. J. Comput. Geom. Appl., 2(2):163?173, 1992.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich. Geometic partitioning made easier, even in parallel.Proc. 9th Ann. ACM Symp. on Computational Geometry, pp. 73?82, 1993.","DOI":"10.1145\/160985.161002"},{"issue":"3","key":"CR14","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1137\/0221031","volume":"21","author":"J. H. Reif","year":"1992","unstructured":"J. H. Reif and S. Sen. Optimal parallel randomized algorithms for three-dimensional convex hulls and related problems.SIAM J. Comput, 21(3):466?485, 1992.","journal-title":"SIAM J. Comput"},{"key":"CR15","first-page":"869","volume-title":"Handbook of Theoretical Computer Science","author":"R. M. Karp","year":"1990","unstructured":"R. M. Karp and V. Ramachandran. Parallel algorithms for shared memory machines. In J. van Leeuwen, ed.,Handbook of Theoretical Computer Science, pp. 869?941. Elsevier\/MIT Press, Amsterdam\/Cambridge, MA, 1990."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"S. A. Cook","year":"1986","unstructured":"S. A. Cook, C. Dwork, and R. Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes.SIAM J. Comput., 15:87?97, 1986.","journal-title":"SIAM J. Comput."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D. G. Kirkpatrick","year":"1986","unstructured":"D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm?SIAM J. Comput., 15:287?299, 1986.","journal-title":"SIAM J. Comput."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1137\/0220016","volume":"20","author":"H. Edelsbrunner","year":"1991","unstructured":"H. Edelsbrunner and W. Shi. An O(n log2 h) time algorithm for the three-dimensional convex hull problem.SIAM J. Comput., 20:259?277, 1991.","journal-title":"SIAM J. Comput."},{"key":"CR19","unstructured":"B. Chazelle and J. Matousek. Derandomizing an output-sensitive convex hull algorithm in three dimensions. Technical Report, Department of Computer Science, Princeton University, 1992."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II.Discrete Comput. Geom., 4:387?421, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"M. Ghouse and M. T. Goodrich. In-place techniques for parallel convex hull algorithms.Proc. 3rd ACM Symp. on Parallel Algorithms and Architecture, pp. 192?203, 1991.","DOI":"10.1145\/113379.113397"},{"key":"CR22","first-page":"442","volume-title":"Lecture Notes in Computer Science, vol. 629","author":"W. Preilowski","year":"1992","unstructured":"W. Preilowski, E. Dahlhaus, and G. Wechsung. New parallel algorithms for convex hull and triangulation in 3-dimensional space.Proc. Internat. Symp. on Mathematical Foundations of Computer Science (MFCS 1992), Lecture Notes in Computer Science, vol. 629. pp. 442?450. Springer-Verlag, Berlin, 1992."},{"key":"CR23","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1992","unstructured":"J. J\u00e1J\u00e1.An Introduction to Parallel Algorithms Addison-Wesley, Reading, MA, 1992."},{"key":"CR24","volume-title":"Synthesis of Parallel Algorithms","year":"1993","unstructured":"J. H. Reif, ed.Synthesis of Parallel Algorithms. Morgan Kaufmann, San Mateo, CA, 1993."},{"issue":"4","key":"CR25","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole. Parallel merge sort.SIAM J. Comput., 17(4):770?785, 1988.","journal-title":"SIAM J. Comput."},{"key":"CR26","first-page":"400","volume-title":"Lecture Notes in Computer Science, vol. 443","author":"D. P. Dobkin","year":"1990","unstructured":"D. P. Dobkin and D. G. Kirkpatrick. Determining the separation of preprocessed polyhedra-a unified approach.Proc. 17th Internat. Colloq. on Automata Language Programming, Lecture Notes in Computer Science, vol. 443. pp. 400?413. Springer-Verlag, Berlin, 1990."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0206043","volume":"6","author":"D. T. Lee","year":"1977","unstructured":"D. T. Lee and F. P. Preparata. Location of a point in a planar subdivision and its applications.SIAM J. Comput., 6:594?606, 1977.","journal-title":"SIAM J. Comput."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision.SIAM J. Comput., 15:317?340, 1986.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"CR29","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1137\/0220045","volume":"20","author":"R. Tamassia","year":"1991","unstructured":"R. Tamassia and J. S. Vitter. Parallel transitive closure and point location in planar structures.SIAM J. Comput, 20(4):708?725, 1991.","journal-title":"SIAM J. Comput"},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"R. Tamassia and J. S. Vitter. Optimal cooperative search in fractional cascaded data structures.Proc. 2nd ACM Symp. on Parallel Algorithms and Architecture, pp. 307?316, 1990. To appear inAlgorithmica.","DOI":"10.1145\/97444.97698"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/0743-7315(90)90103-V","volume":"8","author":"R. Cole","year":"1990","unstructured":"R. Cole and O. Zajicek. An optimal parallel algorithm for building a data structure for planar point location.J. Parallel Distrib. Comput, 8:280?285, 1990.","journal-title":"J. Parallel Distrib. Comput"},{"key":"CR32","doi-asserted-by":"crossref","unstructured":"N. M. Amato and F. P. Preparata. An NC1 parallel 3D convex hull algorithm.Proc. 9th Ann. ACM Symp. on Computational Geometry, pp. 289?297, 1993.","DOI":"10.1145\/160985.161152"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293667.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01293667\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T13:35:56Z","timestamp":1586180156000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01293667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,8]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,8]]}},"alternative-id":["BF01293667"],"URL":"https:\/\/doi.org\/10.1007\/bf01293667","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,8]]}}}