{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T16:15:25Z","timestamp":1782317725892,"version":"3.54.5"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1996,12,1]],"date-time":"1996-12-01T00:00:00Z","timestamp":849398400000},"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":[[1996,12]]},"DOI":"10.1007\/bf01944352","type":"journal-article","created":{"date-parts":[[2005,7,31]],"date-time":"2005-07-31T16:15:27Z","timestamp":1122826527000},"page":"569-617","source":"Crossref","is-referenced-by-count":10,"title":["A nearly optimal deterministic parallel Voronoi diagram algorithm"],"prefix":"10.1007","volume":"16","author":[{"given":"R.","family":"Cole","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. T.","family":"Goodrich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C. \u00d3.","family":"D\u00fanlaing","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"3","key":"BF01944352_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 (1988). Parallel computational geometry.Algorithmica,3(3), 293\u2013328.","journal-title":"Algorithmica"},{"key":"BF01944352_CR2","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1016\/0898-1221(85)90105-1","volume":"11","author":"M. J. Atallah","year":"1985","unstructured":"M. J. Atallah (1985). Some dynamic computational geometry problems.Computers and Mathematics with Applications,11, 1171\u20131181.","journal-title":"Computers and Mathematics with Applications"},{"issue":"3","key":"BF01944352_CR3","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 (1989). Cascading divide-and-conquer: a technique for designing parallel algorithms.SIAM Journal on Computing,18(3), 499\u2013532.","journal-title":"SIAM Journal on Computing"},{"key":"BF01944352_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 (1988). Parallel algorithms for some functions of two convex polygons.Algorithmica,3, 535\u2013548.","journal-title":"Algorithmica"},{"key":"BF01944352_CR5","unstructured":"F. Aurenhammer (1990). Voronoi Diagrams\u2014a Survey of a Fundamental Geometric Data Structure. Technical report, FB Mathematik Serie B, Freie Universit\u00e4t Berlin."},{"key":"BF01944352_CR6","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0890-5401(91)90031-V","volume":"94","author":"P. Bhatt","year":"1991","unstructured":"P. Bhatt, K. Diks, T. Hagerup, V. Prasad, T. Radzik, and S. Saxena (1991). Improved deterministic parallel integer sorting.Information and Computation,94, 29\u201347.","journal-title":"Information and Computation"},{"issue":"3","key":"BF01944352_CR7","first-page":"227","volume":"2","author":"L. Boxer","year":"1989","unstructured":"L. Boxer and R. Miller (1989). Parallel dynamic computational geometry.Journal of New Generation Computer Systems,2(3), 227\u2013246.","journal-title":"Journal of New Generation Computer Systems"},{"key":"BF01944352_CR8","unstructured":"A. Chow (1980). Parallel Algorithms for Geometrie Problems. Ph.D. thesis, Computer Science Department, University of Illinois."},{"key":"BF01944352_CR9","first-page":"432","volume-title":"Proc. 17th ICALP. LNCS, vol. 443","author":"R. Cole","year":"1990","unstructured":"R. Cole, M. Goodrich, and C. \u00d3 D\u00fanlaing (1990). Merging free trees in parallel for efficient Voronoi diagram construction.Proc. 17th ICALP. LNCS, vol. 443. Springer-Verlag, Berlin, pp. 432\u2013445."},{"key":"BF01944352_CR10","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0167-8191(89)90011-2","volume":"12","author":"D. Evans","year":"1989","unstructured":"D. Evans and I. Stojmenovi\u0107 (1989). On parallel computation of Voronoi diagrams.Parallel Computing,12, 121\u2013125.","journal-title":"Parallel Computing"},{"key":"BF01944352_CR11","volume-title":"M.Sc. dissertation","author":"A. Farrell","year":"1994","unstructured":"A. Farrell (1994). Fortune's Voronoi sweepline algorithm for convex sites. M.Sc. dissertation, Department of Mathematics, Trinity College, Dublin."},{"key":"BF01944352_CR12","volume-title":"Synthesis of Parallel Algorithms","author":"F. Fich","year":"1993","unstructured":"F. Fich (1993). The complexity of computation on the parallel random access machine. InSynthesis of Parallel Algorithms, ed. J. Reif. Morgan Kaufmann, Los Altos, CA."},{"key":"BF01944352_CR13","doi-asserted-by":"crossref","unstructured":"F. Fich and V. Ramachandran (1990). Lower bounds for parallel computation on linked structures.Proc. Annual ACM Symp. on Parallel Algorithms and Architectures, Crete, pp. 109\u2013116.","DOI":"10.1145\/97444.97676"},{"issue":"2","key":"BF01944352_CR14","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S. Fortune","year":"1987","unstructured":"S. Fortune (1987). A sweep-line algorithm for Voronoi diagrams.Algorithmica,2(2), 153\u2013174.","journal-title":"Algorithmica"},{"key":"BF01944352_CR15","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/BF01188708","volume":"9","author":"M. T. Goodrich","year":"1993","unstructured":"M. T. Goodrich, C. \u00d3 D\u00fanlaing, and C. Yap (1993). Constructing the Voronoi diagram of a set of line segments in parallel.Algorithmica,9, 128\u2013141.","journal-title":"Algorithmica"},{"key":"BF01944352_CR16","volume-title":"Algebraic Topology-A First Course","author":"M. Greenberg","year":"1981","unstructured":"M. Greenberg and J. Harper (1981).Algebraic Topology-A First Course. Benjamin\/Cummings, Menlo Park, CA."},{"key":"BF01944352_CR17","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/282918.282923","volume":"4","author":"L. Guibas","year":"1985","unstructured":"L. Guibas and J. Stolfi (1985). Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.ACM Transactions on Graphics,4, 74\u2013123.","journal-title":"ACM Transactions on Graphics"},{"issue":"10","key":"BF01944352_CR18","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1109\/TC.1983.1676138","volume":"32","author":"C. Kruskal","year":"1983","unstructured":"C. Kruskal (1983). Searching, merging, and sorting in parallel computation.IEEE Transactions on Computers,32(10), 942\u2013946.","journal-title":"IEEE Transactions on Computers"},{"key":"BF01944352_CR19","doi-asserted-by":"crossref","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir (1985). The power of parallel prefix. 1985Internat. Conf. on Parallel Processing, pp. 180\u2013185.","DOI":"10.1109\/TC.1985.6312202"},{"key":"BF01944352_CR20","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"R. E. Ladner","year":"1980","unstructured":"R. E. Ladner and M. J. Fischer (1980). Parallel prefix computation.Journal of the Association for Computing Machinery,27, 831\u2013838.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF01944352_CR21","volume-title":"Graduate Texts in Mathematics, No. 47","author":"E. Moise","year":"1977","unstructured":"E. Moise (1977).Geometric Topology in Dimensions 2 and 3. Graduate Texts in Mathematics, No. 47. Springer-Verlag, New York."},{"key":"BF01944352_CR22","series-title":"Cambridge International Series on Parallel Computation, Vol. 4","first-page":"77","volume-title":"Lectures on Parallel Computation","author":"C. \u00d3 D\u00fanlaing","year":"1993","unstructured":"C. \u00d3 D\u00fanlaing (1993). Parallel computational geometry. InLectures on Parallel Computation, ed. A. Gibbons and P. Spirakis. Cambridge International Series on Parallel Computation, Vol. 4. Cambridge University Press, Cambridge, pp. 77\u2013108."},{"key":"BF01944352_CR23","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(87)90058-2","volume":"51","author":"I. Parberry","year":"1987","unstructured":"I. Parberry (1987). On the time required to sumn semigroup elements on a parallel machine with simultaneous writes.Theoretical Computer Science,51, 239\u2013247.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"BF01944352_CR24","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 (1992). Optimal parallel algorithms for 3-dimensional convex hulls and related problems.SIAM Journal on Computing,21(3), 466\u2013485.","journal-title":"SIAM Journal on Computing"},{"key":"BF01944352_CR25","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey (1975). Closest-point problems.Proc. 15th IEEE Symp. on Foundations of Computer Science, pp. 151\u2013162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"BF01944352_CR26","volume-title":"CBMS-NSF Regional Conference Series in Applied Mathematics, No. 44","author":"R. Tarjan","year":"1983","unstructured":"R. Tarjan (1983).Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics, No. 44. SIAM, Philadelphia, PA."},{"issue":"3","key":"BF01944352_CR27","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. Valiant","year":"1975","unstructured":"L. Valiant (1975). Parallelism in comparison problems.SIAM Journal on Computing,4(3), 348\u2013355.","journal-title":"SIAM Journal on Computing"},{"key":"BF01944352_CR28","unstructured":"H. Wagener (1985). Optimally Parallel Algorithms for Convex Hull Determination. Manuscript, Technical University of Berlin."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01944352.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01944352\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01944352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T13:49:45Z","timestamp":1586353785000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01944352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["BF01944352"],"URL":"https:\/\/doi.org\/10.1007\/bf01944352","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}