{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,16]],"date-time":"2025-11-16T02:11:50Z","timestamp":1763259110296},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540194873"},{"type":"electronic","value":"9783540392880"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-19487-8_21","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:12:02Z","timestamp":1330200722000},"page":"190-198","source":"Crossref","is-referenced-by-count":7,"title":["An optimal expected-time parallel algorithm for Voronoi diagrams"],"prefix":"10.1007","author":[{"given":"Christos","family":"Levcopoulos","sequence":"first","affiliation":[]},{"given":"Jyrki","family":"Katajainen","sequence":"additional","affiliation":[]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, B. Chazelle, L. Guibas, C. O'Dunlaing, and C. Yap, Parallel Computational Geometry, in Proc. 25th Annual IEEE Symposium on Foundations of Computer Science 1985, 468\u2013477.","DOI":"10.1109\/SFCS.1985.42"},{"key":"21_CR2","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, Journal of Parallel and Distributed Computing 3, 492\u2013507, 1986.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"M.J. Atallah and M.T. Goodrich, Efficient Plane Sweeping in Parallel, Proc. of the 2nd Ann. Symposium on Computational Geometry, Yorktown Heights, 1986.","DOI":"10.1145\/10515.10539"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"J.L. Bentley, B.W. Weide, A.C. Yao, Optimal expected-time algorithms for closest point problems, ACM Transactions on Mathematical Software 6, pp. 563\u2013580.","DOI":"10.1145\/355921.355927"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"B.C. Chazelle, Computational Geometry on a Systolic Chip, IEEE Trans. on Comp., C-33 pp. 774\u2013785.","DOI":"10.1109\/TC.1984.1676494"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"P.J. Green, R. Sibson, Computing Dirichlet tessellations in the plane, The Computer Journal 21, pp. 168\u2013173.","DOI":"10.1093\/comjnl\/21.2.168"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"L.J. Guibas, J. Stofli, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Transactions on Graphics 4, pp. 74\u2013123.","DOI":"10.1145\/282918.282923"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"S. Fortune, A Sweepline Algorithm for Voronoi Diagrams, Proc. of the 2nd Ann. Symposium on Computational Geometry, Yorktown Heights, 1986.","DOI":"10.1145\/10515.10549"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"S. Fortune and J. Wyllie, Parallelism in random access machines, in Proc. 21st Annual ACM Sympos. on Theory of Comput., San Diego, California, 1978, pp. 114\u2013118.","DOI":"10.1145\/800133.804339"},{"key":"21_CR10","unstructured":"J. Katajainen, Bucketing and Filtering in Computational Geometry, Ph. D. dissertation, University of Turku."},{"key":"21_CR11","unstructured":"R. Miller, Q.F. Stout, Computational Geometry on a mesh-connected computer, Proc. Int. Conf. on Parallel Processing, 1984."},{"key":"21_CR12","unstructured":"F.P. Preparata and M.I. Shamos, Computational Geometry, An Introduction, Texts and Monographs in Computer Science, Springer Verlag, New York."},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"J.H. Reif, An Optimal Parallel Algorithm for Integer Sorting, Proc. 26th Ann. Symp. on Foundations of Computer Science, 1985.","DOI":"10.1109\/SFCS.1985.9"},{"key":"21_CR14","unstructured":"S. Rajasekaran and S. Sen, On parallel sorting, Tech. Rept CS-187-38, Dept of Computer Science, Duke University."}],"container-title":["Lecture Notes in Computer Science","SWAT 88"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-19487-8_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:17:19Z","timestamp":1605644239000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-19487-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540194873","9783540392880"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-19487-8_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}