{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:44Z","timestamp":1759637684783},"publisher-location":"Berlin, Heidelberg","reference-count":20,"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_30","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:37:54Z","timestamp":1330252674000},"page":"326-337","source":"Crossref","is-referenced-by-count":5,"title":["Computing the L 1-diameter and center of a simple rectilinear polygon in parallel"],"prefix":"10.1007","author":[{"given":"Sven","family":"Schuierer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"30_CR1","volume-title":"NC-Algorithms for Minimum Link Paths and Related Problems","author":"V. Chandru","year":"1992","unstructured":"V. Chandru, S.K. Ghosh, A. Maheshwari, V. T. Rajan, and S. Saluja. NC-Algorithms for Minimum Link Paths and Related Problems. TR, Tata Institute of Fundamental Research, Bombay, 1992."},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Bernard Chazelle. Triangulating a simple polygon in linear time. In Proc. 31st IEEE Symp. on Foundations of Computer Science, pages 220\u2013230, 1990.","DOI":"10.1109\/FSCS.1990.89541"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"K.L. Clarkson, R. Cole, and R.E. Tarjan. Randomized parallel algorithms for trapezoidal decomposition. In Proc. 7th ACM Symp. on Computational Geometry, pages 152\u2013161, 1991.","DOI":"10.1145\/109648.109665"},{"key":"30_CR4","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02293040","volume":"8","author":"H. N. Djidjev","year":"1992","unstructured":"H.N. Djidjev, A. Lingas, and J.-R. Sack. An O(n log n) algorithm for computing the link center of a simple polygon. Discrete and Computational Geometry, 8:131\u2013152, 1992.","journal-title":"Discrete and Computational Geometry"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"S.K. Ghosh and A. Maheshwari. Parallel Algorithms for All Minimum Link Paths and Link Center Problems. In O. Nurmi, E. Ukkonnen, editors, Proc. 3rd Scand. Workshop on Algorithm Theory, pages 106\u2013117, LNCS 621, 1992.","DOI":"10.1007\/3-540-55706-7_10"},{"key":"30_CR6","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0196-6774(89)90032-1","volume":"10","author":"M. T. Goodrich","year":"1989","unstructured":"M.T. Goodrich. Triangulating a polygon in parallel. Journal of Algorithms, 10:327\u2013351, 1989.","journal-title":"Journal of Algorithms"},{"key":"30_CR7","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, S.B. Shauck, and S. Guha. Parallel methods for visibility and shortest path problems in simple polygons. In Proc. 7th ACM Symp. on Computational Geometry, pages 73\u201382, 1991.","DOI":"10.1145\/98524.98539"},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"J. Hershberger. Optimal parallel algorithms for triangulated simple polygons. In Proc. 8th ACM Symp. on Computational Geometry, pages 33\u201342, 1992.","DOI":"10.1145\/142675.142687"},{"key":"30_CR9","unstructured":"J. J\u00e1J\u00e1. An Introduction to Parallel Algorithms. Addison-Wesley, 1992."},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"J.Hershberger and S. Suri. Matrix searching with the shortest path metric. In 25th ACM Symp. on Theory of Computing, pages 485\u2013494, 1993.","DOI":"10.1145\/167088.167220"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Yan Ke. An efficient algorithm for link-distance problems. In Proc. 5th Symp. on Computational Geometry, pages 69\u201378, 1989.","DOI":"10.1145\/73833.73841"},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"W. Lenhart, R. Pollack, J. Sack, R. Seidel, M. Sharir, S. Suri, G. Toussaint, S. Whitesides, and C. Yap. Computing the link center of a simple polygon. Discrete and Computational Geometry 3:281\u2013293.","DOI":"10.1007\/BF02187913"},{"key":"30_CR13","volume-title":"PhD thesis","author":"C. Levcopoulos","year":"1987","unstructured":"Christos Levcopoulos. Heuristics for Minimum Decompositions of Polygons. PhD thesis, University of Link\u00f6ping, Link\u00f6ping, Sweden, 1987."},{"key":"30_CR14","doi-asserted-by":"crossref","unstructured":"A. Lingas, A. Maheshwari, and J.-R. Sack. Optimal parallel algorithms for rectilinear link distance problems. Algorithmica, to appear.","DOI":"10.1007\/BF01206332"},{"issue":"7","key":"30_CR15","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1109\/43.144850","volume":"11","author":"K. M. McDonalds","year":"1992","unstructured":"K. M. McDonalds and I. G. Peters. Smallest paths in simple rectilinear polygons. IEEE Transactions on Computer-Aided Design, 11(7):864\u2013875, 1992.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"B. J. Nilsson and S. Schuierer. Computing the rectilinear link diameter of a polygon. In H. Bieri, editor, Proc. Workshop on Computational Geometry, pages 203\u2013216, LNCS 553, 1991.","DOI":"10.1007\/3-540-54891-2_15"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"B.J. Nilsson and S. Schuierer. An optimal algorithm for the rectilinear link center of a rectilinear polygon. In N. Santoro F. Dehne, J.-R. Sack, editor, Proc. 2nd Workshop on Algorithms and Datastructures, pages 249\u2013260, LNCS 519, 1991.","DOI":"10.1007\/BFb0028267"},{"issue":"6","key":"30_CR18","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1007\/BF02187751","volume":"4","author":"R. Pollack","year":"1989","unstructured":"R. Pollack, M. Sharir, and G. Rote. Computing the geodesic center of a simple polygon. Discrete and Computational Geometry, 4(6):611\u2013626, 1989.","journal-title":"Discrete and Computational Geometry"},{"key":"30_CR19","doi-asserted-by":"crossref","unstructured":"S. Schuierer. An Optimal Algorithm to Compute the L 1-Diameter and Center of a Simple Rectilinear Polygon. Technical Report 49, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, 1994.","DOI":"10.1007\/3-540-58218-5_30"},{"key":"30_CR20","unstructured":"M. van de Vel. Theory of Convex Structures. Mathematical Library, North-Holland, 1993."}],"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_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:18:50Z","timestamp":1605629930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}