{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,12]],"date-time":"2023-01-12T15:31:47Z","timestamp":1673537507232},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"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":[[1992,6]]},"DOI":"10.1007\/bf01758749","type":"journal-article","created":{"date-parts":[[2005,6,15]],"date-time":"2005-06-15T06:49:08Z","timestamp":1118818148000},"page":"3-23","source":"Crossref","is-referenced-by-count":19,"title":["Optimal parallel algorithms for point-set and polygon problems"],"prefix":"10.1007","volume":"7","author":[{"given":"Richard","family":"Cole","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"No. 3","key":"BF01758749_CR1","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, Vol. 3, No. 3, 1988, pp. 293\u2013328.","journal-title":"Algorithmica"},{"issue":"No. 3","key":"BF01758749_CR2","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1137\/0218035","volume":"18","author":"M. J. Atallah","year":"1989","unstructured":"M. J. Atallah, R. Cole, and M. T. Goodrich, Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms,SIAM J. Comput., Vol. 18, No. 3, 1989, pp. 499\u2013532 (appeared in preliminary form inProc. 28th IEEE Symp. on Foundations of Computer Science, 1987, pp. 151\u2013160).","journal-title":"SIAM J. Comput."},{"key":"BF01758749_CR3","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. Vol. 3, 1986, pp. 492\u2013507.","journal-title":"J. Parallel Distrib. Comput."},{"issue":"No. 4","key":"BF01758749_CR4","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, Vol. 3, No. 4, 1988, pp. 535\u2013548.","journal-title":"Algorithmica"},{"key":"BF01758749_CR5","doi-asserted-by":"crossref","unstructured":"J. L. Bentley and M. I. Shamos, Divide-and-Conquer in Multidimensional Space,Proc. 8th ACM Symp. on Theory of Computing, 1976, pp. 220\u2013230.","DOI":"10.1145\/800113.803652"},{"key":"BF01758749_CR6","unstructured":"G. Bilardi and A. Nicolau, Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared Memory Machines, TR 86-769, Dept. of Computer Science, Cornell University, August 1986."},{"key":"BF01758749_CR7","unstructured":"A. Chow, Parallel Algorithms for Geometric Problems, Ph.D. thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, 1980."},{"issue":"No. 4","key":"BF01758749_CR8","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., Vol. 17, No. 4, August 1988. pp. 770\u2013785.","journal-title":"SIAM J. Comput."},{"key":"BF01758749_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987."},{"issue":"No. 3","key":"BF01758749_CR10","first-page":"105","volume":"9","author":"A. Fournier","year":"1979","unstructured":"A. Fournier and Z. Kedem, Comments on the All-Nearest-Neighbor Problem for Convex Polygons,Inform. Process. Lett., Vol. 9, No. 3, 1979, pp. 105\u2013107.","journal-title":"Inform. Process. Lett."},{"key":"BF01758749_CR11","unstructured":"M. T. Goodrich, Efficient Parallel Techniques for Computational Geometry, Ph.D. thesis, Dept. of Computer Science, Purdue University, August 1987."},{"key":"BF01758749_CR12","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0020-0190(87)90002-0","volume":"26","author":"M. T. Goodrich","year":"1987","unstructured":"M. T. Goodrich, Finding the Convex Hull of a Sorted Point Set in Parallel,Inform. Process. Lett., Vol. 26, December 1987, pp. 173\u2013179.","journal-title":"Inform. Process. Lett."},{"key":"BF01758749_CR13","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0196-6774(89)90032-1","volume":"10","author":"M. T. Goodrich","year":"1989","unstructured":"M. T. Goodrich, Triangulating a Polygon in Parallel,J. Algorithms, Vol. 10, 1989, pp. 327\u2013351.","journal-title":"J. Algorithms"},{"key":"BF01758749_CR14","doi-asserted-by":"crossref","unstructured":"L. Guibas, L. Ramshaw, and J. Stolfi, A Kinetic Framework for Computational Geometry,Proc. 24th IEEE Symp. on Foundations of Computer Science, 1983, pp. 100\u2013111.","DOI":"10.1109\/SFCS.1983.1"},{"key":"BF01758749_CR15","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir, The Power of Parallel Prefix,Proc. 1985 IEEE Internat. Conf. on Parallel Processing, pp. 180\u2013185."},{"key":"BF01758749_CR16","doi-asserted-by":"crossref","unstructured":"R. E. Ladner and M. J. Fischer, Parallel Prefix Computation,J. Assoc. Comput. Mach., October 1980, pp. 831\u2013838.","DOI":"10.1145\/322217.322232"},{"issue":"No. 4","key":"BF01758749_CR17","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0020-0190(78)90066-2","volume":"7","author":"D. T. Lee","year":"1978","unstructured":"D. T. Lee and F. P. Preparata, The All-Nearest-Neighbor Problem for Convex Polygons,Inform. Process. Lett., Vol. 7, No. 4, June 1978, pp. 189\u2013192.","journal-title":"Inform. Process. Lett."},{"issue":"No. 3","key":"BF01758749_CR18","first-page":"414","volume":"26","author":"D. T. Lee","year":"1979","unstructured":"D. T. Lee and F. P. Preparata, An Optimal Algorithm for Finding the Kernel of a Polygon,J. Assoc. Comput. Mach., Vol. 26, No. 3, July 1979, pp. 414\u2013421.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"No. 12","key":"BF01758749_CR19","first-page":"872","volume":"33","author":"D. T. Lee","year":"1984","unstructured":"D. T. Lee and F. P. Preparata, Computational Geometry\u2014A Survey,IEEE Trans. Comput., Vol. 33, No. 12, December 1984, pp. 872\u20131101.","journal-title":"IEEE Trans. Comput."},{"key":"BF01758749_CR20","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0304-3975(79)90055-0","volume":"8","author":"F. P. Preparata","year":"1979","unstructured":"F. P. Preparata and D. E. Muller, Finding the Intersection ofn Half-Spaces in TimeO(n logn), Theoret. Comput. Sci., Vol. 8, 1979, pp. 45\u201355.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01758749_CR21","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":"BF01758749_CR22","doi-asserted-by":"crossref","unstructured":"M. I. Shamos, Geometric Complexity,Proc. 7th ACM Symp. on Theory of Computing, 1975, pp. 224\u2013233.","DOI":"10.1145\/800116.803772"},{"key":"BF01758749_CR23","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey, Closest-Point Problems,Proc. 15th IEEE Symp. on Foundations of Computer Science, 1975, pp. 151\u2013162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"BF01758749_CR24","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Y. Shiloach and U. Vishkin, Finding the Maximum, Merging, and Sorting in a Parallel Computation Model,J. Algorithms, Vol. 2, 1981, pp. 88\u2013102.","journal-title":"J. Algorithms"},{"key":"BF01758749_CR25","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/0217010","volume":"17","author":"R. E. Tarjan","year":"1988","unstructured":"R. E. Tarjan and C. J. Van Wyk, AnO(n log logn)-Time Algorithm for Triangulating a Simple Polygon,SIAM J. Comput., Vol. 17, 1988, pp. 143\u2013178.","journal-title":"SIAM J. Comput."},{"key":"BF01758749_CR26","unstructured":"G. T. Toussaint, Solving Geometric Problems with Rotating Calipers,Proc. IEEE MELECON '83, Athens, May 1983."},{"key":"BF01758749_CR27","unstructured":"H. Wagener, Optimally Parallel Algorithms for Convex Hull Determination, Manuscript, 1985."},{"issue":"No. 4","key":"BF01758749_CR28","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(79)90021-8","volume":"8","author":"C. C. Yang","year":"1979","unstructured":"C. C. Yang and D. T. Lee, A Note on the All-Nearest-Neighbor Problem for Convex Polygons,Inform. Process. Lett, Vol. 8, No. 4, 1979, pp. 193\u2013194.","journal-title":"Inform. Process. Lett"},{"issue":"No. 2","key":"BF01758749_CR29","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF01762118","volume":"3","author":"C.-K. Yap","year":"1988","unstructured":"C.-K. Yap, Parallel Triangulation of a Polygon in Two Calls to the Trapezoidal Map,Algorithmica, Vol. 3, No. 2, 1988, pp. 279\u2013288.","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758749.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01758749\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758749","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T12:25:40Z","timestamp":1557318340000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01758749"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":29,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01758749"],"URL":"https:\/\/doi.org\/10.1007\/bf01758749","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}