{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:36:19Z","timestamp":1725456979081},"publisher-location":"Berlin\/Heidelberg","reference-count":25,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540528261"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0032049","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T06:05:31Z","timestamp":1134281131000},"page":"432-445","source":"Crossref","is-referenced-by-count":16,"title":["Merging free trees in parallel for efficient voronoi diagram construction"],"prefix":"10.1007","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"}]},{"given":"Colm \u00d3","family":"D\u00fanlaing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"33_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, \u201cParallel Computational Geometry,\u201d Algorithmica, 3(3), 1988, 293\u2013328.","journal-title":"Algorithmica"},{"issue":"3","key":"33_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, \u201cCascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms,\u201d SIAM J. on Comput., 18(3), 1989, 499\u2013532.","journal-title":"SIAM J. on Comput."},{"key":"33_CR3","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, \u201cParallel Algorithms for Some Functions of Two Convex Polygons,\u201d Algorithmica, 3, 1988, 535\u2013548.","journal-title":"Algorithmica"},{"key":"33_CR4","doi-asserted-by":"crossref","unstructured":"M.J. Atallah, M.T. Goodrich, and S.R. Kosaraju, \u201cParallel Algorithms for Evaluating Sequences of Set-Manipulation Operations,\u201d Lecture Notes 319: AWOC 88, Springer-Verlag, 1988, 1\u201310.","DOI":"10.1007\/BFb0040368"},{"key":"33_CR5","doi-asserted-by":"crossref","unstructured":"O. Berkman and U. Vishkin, \u201cRecursive *-tree Data Structure,\u201d Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, 496\u2013501.","DOI":"10.1109\/SFCS.1989.63478"},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"B. Chazelle and L.J. Guibas, \u201cFractional Cascading: I. A Data Structuring Technique,\u201d Algorithmica, Vol. 1, No. 2, pp. 133\u2013162.","DOI":"10.1007\/BF01840440"},{"key":"33_CR7","unstructured":"A. Chow, \u201cParallel Algorithms for Geometric Problems,\u201d Ph.D. thesis, Comp. Sci. Dept., Univ. of Illinois, 1980."},{"issue":"4","key":"33_CR8","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole, \u201cParallel Merge Sort,\u201d SIAM J. Comput., 17(4), 1988, 770\u2013785.","journal-title":"SIAM J. Comput."},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"N. Dadoun and D.G. Kirkpatrick, \u201cParallel processing for efficient subdivision search,\u201d Proc. 3rd Annual Symposium on Computational Geometry, 1987, 205\u2013214.","DOI":"10.1145\/41958.41980"},{"key":"33_CR10","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)."},{"key":"33_CR11","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02187681","volume":"1","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner and R. Seidel, \u201cVoronoi Diagrams and Arrangements,\u201d Discrete Comput. Geom., 1, 1986, 25\u201344.","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"33_CR12","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S. Fortune","year":"1987","unstructured":"S. Fortune, \u201cA sweep-line algorithm for Voronoi diagrams,\u201d Algorithmica, 2(2), 1987, 153\u2013174.","journal-title":"Algorithmica"},{"key":"33_CR13","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, C. \u00d3 D\u00fanlaing, and C. Yap \u201cComputing the Voronoi Diagram of a Set of Line Segments in Parallel,\u201d Lecture Notes 382: WADS '89, Springer-Verlag, 1989, 12\u201323.","DOI":"10.1007\/3-540-51542-9_3"},{"key":"33_CR14","doi-asserted-by":"crossref","unstructured":"R. Klein, Concrete and abstract Voronoi diagrams, Springer LNCS 400, 1989.","DOI":"10.1007\/3-540-52055-4"},{"issue":"10","key":"33_CR15","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1109\/TC.1983.1676138","volume":"C-32","author":"C. Kruskal","year":"1983","unstructured":"C. Kruskal, \u201cSearching, merging, and sorting in parallel computation,\u201d IEEE Transactions on Computers, C-32(10), 1983, 942\u2013946.","journal-title":"IEEE Transactions on Computers"},{"key":"33_CR16","doi-asserted-by":"crossref","unstructured":"Kruskal, C.P., Rudolph, L., and Snir, M., \u201cThe Power of Parallel Prefix,\u201d 1985 Int. Conf. on Parallel Processing, 180\u2013185.","DOI":"10.1109\/TC.1985.6312202"},{"key":"33_CR17","doi-asserted-by":"crossref","unstructured":"Ladner, R.E., and Fischer, M.J., \u201cParallel Prefix Computation,\u201d J. ACM, October 1980, 831\u2013838.","DOI":"10.1145\/322217.322232"},{"key":"33_CR18","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Meiser, S., and \u00d3 D\u00fanlaing, C., \u201cOn the construction of abstract Voronoi diagrams,\u201d Proc 7th STACS (Rouen 1990) Springer LNCS 415, 227\u2013239.","DOI":"10.1007\/3-540-52282-4_46"},{"key":"33_CR19","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, NY, 1985."},{"key":"33_CR20","doi-asserted-by":"crossref","unstructured":"J.H. Reif and S. Sen, \u201cPolling: A New Randomized Sampling Technique for Computational Geometry,\u201d Proc. 21st ACM Symp. on Theory of Computing, 1989, 394\u2013393.","DOI":"10.1145\/73007.73045"},{"key":"33_CR21","doi-asserted-by":"crossref","unstructured":"M.I. Shamos, \u201cGeometric Complexity,\u201d Proc. 7th ACM Symp. on Theory of Computing, 1975, 224\u2013233.","DOI":"10.1145\/800116.803772"},{"key":"33_CR22","doi-asserted-by":"crossref","unstructured":"M.I. Shamos and D. Hoey, \u201cClosest-Point Problems,\u201d Proc. 15th IEEE Symp. on Foundations of Computer Science, 1975, 151\u2013162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"33_CR23","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1137\/0214051","volume":"14","author":"M. Snir","year":"1985","unstructured":"M. Snir, \u201cOn Parallel Searching,\u201d SIAM J. on Comput., Vol. 14, 1985, 688\u2013707.","journal-title":"SIAM J. on Comput."},{"issue":"3","key":"33_CR24","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. Valiant","year":"1975","unstructured":"L. Valiant, \u201cParallelism in comparison problems,\u201d SIAM Journal on Computing, 4:3, 1975, 348\u2013355.","journal-title":"SIAM Journal on Computing"},{"key":"33_CR25","unstructured":"H. Wagener, \u201cOptimally Parallel Algorithms for Convex Hull Determination,\u201d manuscript, 1985."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0032049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T13:44:39Z","timestamp":1586612679000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0032049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540528261"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/bfb0032049","relation":{},"subject":[]}}