{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:18Z","timestamp":1725664098877},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_7","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:38:13Z","timestamp":1330270693000},"page":"73-82","source":"Crossref","is-referenced-by-count":0,"title":["A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, L.J. Guibas, J. Saxe, and P.W. Shor. A Linear-Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon. Discrete and Computational Geometry 2, 1987, Springer Verlag.","DOI":"10.1145\/28395.28400"},{"key":"7_CR2","unstructured":"F. Aurenhammer. Voronoi Diagrams\u2014A Survey. Tech. Rep., Graz Technical University, 1988."},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"O. Berkman, D. Breslauer, Z. Galil, B. Schieber and U. Vishkin. Highly Parallelizable Problems. Proc. 21st ACM STOC, pp. 309\u2013319.","DOI":"10.1145\/73007.73036"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"R. Cole and M.T. Goodrich. Optimal Parallel Algorithms for Polygon and Point-Set Problems. Proc. 4th ACM Symp. on Computational Geometry, 1988.","DOI":"10.1145\/73393.73414"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"R. Cole, M.T. Goodrich and C. \u00d3 D\u00fanlaing. Merging Free Trees in Parallel for Efficient Voronoi Diagram Construction. Proc. 17th ICALP, LNCS 443, Springer Verlag, pp. 432\u2013445.","DOI":"10.1007\/BFb0032049"},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin. Approximate Parallel Scheduling. Part 1: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time. SIAM J. Comput. 17(1), 1988, pp. 128\u2013142.","journal-title":"SIAM J. Comput."},{"key":"7_CR7","unstructured":"P. Chew. Building Voronoi Diagrams for Convex Polygons in Linear Expected Time. Manuscript (1986)."},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"K.L. Clarkson. New applications of random sampling in computational geometry. Discrete and Computational Geometry, 1987, pp. 195\u2013222.","DOI":"10.1007\/BF02187879"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"K.L. Clarkson. Applications of random sampling in computational geometry II. Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 1\u201311.","DOI":"10.1145\/73393.73394"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"K.L. Clarkson and P. Shor. Algorithms for diametral pairs and convex hulls that are optimal, randomized and incremental. Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 12\u201322.","DOI":"10.1145\/73393.73395"},{"issue":"No1","key":"7_CR11","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1142\/S021819599200007X","volume":"2","author":"O. Devillers","year":"1992","unstructured":"O. Devillers. Randomization yields simple O(n log* n) algorithms for difficult \u03a9(n) problems. International Journal of Computational Geometry and Applications, Vol 2, No 1 (1992), pp. 97\u2013111.","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"H. Djidjev and A. Lingas. On Computing the Voronoi Diagram for Restricted Planar Figures. Proc. WADS'91, pp. 54\u201364, LNCS, Springer Verlag. To appear in IJCGA.","DOI":"10.1007\/BFb0028250"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner. Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science 10, 1987, Springer Verlag.","DOI":"10.1007\/978-3-642-61568-9"},{"key":"7_CR14","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/282918.282923","volume":"4","author":"L. J. Guibas","year":"1985","unstructured":"L.J. Guibas and J. Stolfi. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Trans. Graphics 4, 1985, pp. 74\u2013123.","journal-title":"ACM Trans. Graphics"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"R. Klein and A. Lingas. A linear-time randomized algorithm for the bounded Voronoi diagram of a simple polygon. Proc. 9th ACM Symposium on Computational Geometry, San Diego, 1993.","DOI":"10.1145\/160985.161008"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"R. Klein and A. Lingas. Hamiltonian abstract Voronoi diagrams in linear time. Manuscript, 1993.","DOI":"10.1007\/3-540-58325-4_161"},{"key":"7_CR17","unstructured":"R. Klein and A. Lingas. A note on generalizations of Chew's algorithm for the Voronoi diagram of a convex polygon. Proc. of the 5th CCCG, pp. 370\u2013374."},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"R. M. Karp and V. Ramachandran, Parallel Algorithms for Shared-Memory Machines. Handbook of Theoretical Computer Science, Edited by, J. van Leeuwen, Volume 1, Elsevier Science Publishers B.V., 1990.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"7_CR19","volume-title":"Texts and Monographs in Theoretical Computer Science","author":"F. P. Preparata","year":"1985","unstructured":"F.P. Preparata and M.I. Shamos. Computational Geometry: An Introduction. Texts and Monographs in Theoretical Computer Science, Springer Verlag, New York, 1985."},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"S. Rajasekaran and J.H. Reif. Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms. SIAM Journal on Computing 18(3), pp. 594\u2013607.","DOI":"10.1137\/0218041"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"J.H. Reif and S. Sen. Polling: A New Randomized Sampling Technique for Computational Geometry. Proc. 21st STOC, Seattle, 1989, pp. 394\u2013404.","DOI":"10.1145\/73007.73045"},{"key":"7_CR22","volume-title":"Ph.D. Thesis","author":"H. Wagener","year":"1986","unstructured":"H. Wagener. Parallel Computational Geometry: Exploiting polygonal order for optimally parallel algorithms. Ph.D. Thesis, Techn. Univ. Berlin, 1986."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:18:52Z","timestamp":1605647932000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}