{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:55:16Z","timestamp":1725663316193},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540515425"},{"type":"electronic","value":"9783540482376"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51542-9_3","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:07:06Z","timestamp":1330186026000},"page":"12-23","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Constructing the Voronoi diagram of a set of line segments in parallel"],"prefix":"10.1007","author":[{"given":"Michael T.","family":"Goodrich","sequence":"first","affiliation":[]},{"given":"Colm","family":"\u00d3'D\u00fanlaing","sequence":"additional","affiliation":[]},{"given":"Chee K.","family":"Yap","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"issue":"3","key":"3_CR1","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/BF01762120","volume":"3","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal, B. Chazelle, L. Guibas, C. \u00d3'D\u00fanaling, and C. Yap, \u201cParallel Computational Geometry,\u201d Algorithmica, Vol. 3, No. 3, 1988, 293\u2013328.","journal-title":"Algorithmica"},{"key":"3_CR2","unstructured":"M.J. Atallah, R. Cole, and M.T. Goodrich, \u201cCascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms,\u201d SIAM J. Comput., in press."},{"key":"3_CR3","doi-asserted-by":"publisher","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, \u201cEfficient Parallel Solutions to Some Geometric Problems,\u201d J. of Par. and Dist. Comp., Vol. 3, 1986, 492\u2013507.","journal-title":"J. of Par. and Dist. Comp."},{"key":"3_CR4","doi-asserted-by":"publisher","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, Vol. 3, 1988, 535\u2013548.","journal-title":"Algorithmica"},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1016\/0022-0000(84)90003-5","volume":"29","author":"M. J. Atallah","year":"1985","unstructured":"M.J. Atallah and U. Vishkin, \u201cFinding Euler Tours in Parallel,\u201d J. Comp. and System Sci., Vol. 29, 1985, 330\u2013337.","journal-title":"J. Comp. and System Sci."},{"key":"3_CR6","unstructured":"G. Bilardi and A. Nicolau, \u201cAdaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared Memory Machines,\u201d TR 86-769, Dept. of Comp. Sci., Cornell Univ., August 1986."},{"key":"3_CR7","first-page":"362","volume-title":"Proc. Symp. Models for Perception of Speech and Visual Form","author":"H. Blum","year":"1967","unstructured":"H. Blum, \u201cA Transformation for Extracting New Descriptors of Shape,\u201d Proc. Symp. Models for Perception of Speech and Visual Form, W. Whaten-Dunn, ed., Cambridge, MA: M.I.T. Press, 1967, 362\u2013380."},{"key":"3_CR8","unstructured":"A. Chow, \u201cParallel Algorithms for Geometric Problems,\u201d Ph.D. thesis, Comp. Sci. Dept., Univ. of Illinois at Urbana-Champaign, 1980."},{"issue":"4","key":"3_CR9","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole, \u201cParallel Merge Sort,\u201d SIAM J. Computing, Vol. 17, No. 4, August 1988, 770\u2013785.","journal-title":"SIAM J. Computing"},{"key":"3_CR10","unstructured":"R. Cole and M.T. Goodrich, \u201cOptimal Parallel Algorithms for Polygon and Point-Set Problems,\u201d Algorithmica, in press."},{"key":"3_CR11","unstructured":"R.L. Drysdale, III, \u201cGenerlaized Voronoi Diagrams and Geometric Searching,\u201d Computer Science Report STAN-CS-79-705, Stanford Univ., Ph.D. thesis, 1979."},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"S. Fortune, \u201cA Sweepline Algorithm for Voronoi Diagrams,\u201d Proc. 2nd ACM Symp. on Computational Geometry, 1986, 313\u2013322.","DOI":"10.1145\/10515.10549"},{"key":"3_CR13","unstructured":"M.T. Goodrich, \u201cEfficient Parallel Techniques for Computational Geometry,\u201d Ph.D. thesis, Dept. of Computer Science, Purdue Univ., August 1987."},{"key":"3_CR14","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, \u201cFinding the Convex Hull of a Sorted Point Set in Parallel,\u201d Info. Proc. Letters, Vol. 26, December 1987, 173\u2013179.","journal-title":"Info. Proc. Letters"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"L. Guibas, L. Ramshaw, and J. Stolfi, \u201cA Kinetic Framework for Computational Geometry,\u201d Proc. 24th IEEE Symp. on Found. of Comp. Sci., 1983, 100\u2013111.","DOI":"10.1109\/SFCS.1983.1"},{"key":"3_CR16","unstructured":"R.M. Karp and V. Ramachandran, \u201cA Survey of Parallel Algorithms for Shared-Memory Machines,\u201d to appear in Handbook of Theoretical Computer Science, North-Holland."},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"D.G. Kirkpatrick, \u201cEfficient Computation of Continuous Skeletons,\u201d Proc. 20th IEEE Symp. on Foundations of Computer Science, 1979, 18\u201327.","DOI":"10.1109\/SFCS.1979.15"},{"key":"3_CR18","unstructured":"C.P. Kruskal, L. Rudolph, and M. Snir, \u201cThe Power of Parallel Prefix,\u201d Proc. 1985 IEEE Int. Conf. on Parallel Processing, 180\u2013185."},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"R.E. Ladner and M.J. Fischer, \u201cParallel Prefix Computation,\u201d J. ACM, October 1980, 831\u2013838.","DOI":"10.1145\/322217.322232"},{"issue":"4","key":"3_CR20","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1109\/TPAMI.1982.4767267","volume":"PAMI-4","author":"D. T. Lee","year":"1982","unstructured":"D.T. Lee, \u201cMedial Axis Transformation of a Planar Shape,\u201d IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI-4, No. 4, July 1982, 363\u2013369.","journal-title":"IEEE Trans. on Pattern Analysis and Machine Intelligence"},{"issue":"1","key":"3_CR21","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1137\/0210006","volume":"10","author":"D. T. Lee","year":"1981","unstructured":"D.T. Lee and R.L. Drysdale, III,\u201cGeneralization of Voronoi Diagrams in the Plane,\u201d SIAM Journal on Computing, Vol. 10, No. 1, Feb. 1981, 73\u201387.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"J.S.B. Mitchell, \u201cOn Maximum Flows in Polyhedral Domains,\u201d Proc. 4th ACM Symp. on Computational Geometry, 1988, 341\u2013351.","DOI":"10.1145\/73393.73428"},{"key":"3_CR23","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/0196-6774(85)90021-5","volume":"6","author":"C. \u00d3'D\u00fanlaing","year":"1985","unstructured":"C. \u00d3'D\u00fanlaing and C. Yap, \u201cA \u2018Retraction\u2019 Method for Planning the Motion of a Disc, J. Algorithms, Vol. 6, 1985, 104\u2013111.","journal-title":"J. Algorithms"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"F.P. Preparata, \u201cThe Medial Axis of a Simple Polygon,\u201d Proc. 6th Symp. on Mathematical Foundations of Computer Science, 1977, 443\u2013450.","DOI":"10.1007\/3-540-08353-7_166"},{"key":"3_CR25","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":"3_CR26","unstructured":"G.T. Toussaint, \u201cSolving Geometric Problems with Rotating Calipers,\u201d Proc. IEEE MELECON '83, Athens, Greece, May 1983."},{"key":"3_CR27","unstructured":"H. Wagener, \u201cOptimally Parallel Algorithms for Convex Hull Determination,\u201d unpublished manuscript, September 1985."},{"key":"3_CR28","unstructured":"J.C. Wyllie, \u201cThe Complexity of Parallel Computation,\u201d Ph.D. thesis, Technical Report TR 79-387, Department of Computer Science, Cornell University, 1979."},{"key":"3_CR29","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02187890","volume":"2","author":"C. K. Yap","year":"1987","unstructured":"C.K. Yap, \u201cAn O(n log n) Algorithm for the Voronoi Diagram of a Set of Simple Curve Segments,\u201d Discrete and Computational Geometry, Vol. 2, 1987, 365\u2013393.","journal-title":"Discrete and Computational Geometry"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51542-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T19:08:12Z","timestamp":1578510492000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51542-9_3"}},"subtitle":["Preliminary version"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540515425","9783540482376"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-51542-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"26 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}