{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:31Z","timestamp":1725663271233},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540528463"},{"type":"electronic","value":"9783540471646"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52846-6_91","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:43:18Z","timestamp":1330206198000},"page":"213-224","source":"Crossref","is-referenced-by-count":8,"title":["Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric"],"prefix":"10.1007","author":[{"given":"Mark","family":"Berg","sequence":"first","affiliation":[]},{"given":"Marc","family":"Kreveld","sequence":"additional","affiliation":[]},{"given":"Bengt J.","family":"Nilsson","sequence":"additional","affiliation":[]},{"given":"Mark H.","family":"Overmars","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle, L.J. Guibas. Fractional Cascading: I. A data structuring technique. Algorithmica, 1:133\u2013162, 1986.","journal-title":"Algorithmica"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"K. Clarkson, S. Kapoor, P. Vaidya. Rectilinear Shortest Paths through Polygonal Obstacles in O(n log2n) Time. In Proc. 3rd ACM Symp. on Computational Geometry, pages 251\u2013257, 1987.","DOI":"10.1145\/41958.41985"},{"key":"19_CR3","unstructured":"M. de Berg. On Rectilinear Link Distance. Technical Report RUU-CS-89-13, Department of Computer Science, Utrecht University, 1989."},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"E.W. Dijkstra. A Note on Two Problems in Connection with Graphs. Numer. Math., 1:269\u2013271, 1959.","journal-title":"Numer. Math."},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"H.N. Djidjev, A. Lingas and J. Sack. An O(n log n) time Algorithm for Computing the Link Center in a Simple Polygon. In B. Monien and R. Cori (Eds.) Proceedings STACS '89, Lect. Notes in Comp. Science 349, Springer Verlag, pages 96\u2013107, 1989.","DOI":"10.1007\/BFb0028976"},{"key":"19_CR6","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0734-189X(84)90142-7","volume":"28","author":"H. Edelsbrunner","year":"1984","unstructured":"H. Edelsbrunner, M.H. Overmars, R. Seidel. Some Methods of Computational geometry Applied to Computer Graphics. Computer Vision, Graphics, and Image Processing, 28:92\u2013108, 1984.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"19_CR7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02187714","volume":"4","author":"P.J. Rezende de","year":"1989","unstructured":"P.J. de Rezende, D.T. Lee, Y.F. Wu. Rectilinear Shortest Paths with Rectangular Barriers. Journal of Discrete and Computational Geometry, 4:41\u201353, 1989.","journal-title":"Journal of Discrete and Computational Geometry"},{"key":"19_CR8","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S. Hart","year":"1986","unstructured":"S. Hart and M. Sharir. Nonlinearity of Davenport-Schinzel Sequences and of Generalized Path Compression Schemes. Combinatorica, 6:151\u2013177, 1986.","journal-title":"Combinatorica"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Y. Ke. An Efficient Algorithm for Link Distance Problems. In Proc. 5th ACM Symp. on Computational Geometry, pages 69\u201378, 1989.","DOI":"10.1145\/73833.73841"},{"key":"19_CR10","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1002\/net.3230110307","volume":"11","author":"R.C. Larson","year":"1981","unstructured":"R.C. Larson, V.O. Li. Finding Minimum Rectilinear Distance Paths in the Presence of Barriers. Networks, 11:285\u2013304, 1981.","journal-title":"Networks"},{"key":"19_CR11","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"D.T. Lee","year":"1984","unstructured":"D.T. Lee, F.P. Preparata. Euclidean Shortest Paths in the Presence of Rectilinear Barriers. Networks, 14:393\u2013410, 1984.","journal-title":"Networks"},{"key":"19_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. In Proc. 3rd ACM Symp. on Computational Geometry, pages 1\u201310, 1987.","DOI":"10.1145\/41958.41959"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1145\/359156.359164","volume":"22","author":"T. Lozano-Perez","year":"1979","unstructured":"T. Lozano-Perez, M.A. Wesley. An Algorithm for Planning Collision-free Paths among Polyhedral Obstacles. Communications of the ACM, 22:560\u2013570, 1979.","journal-title":"Communications of the ACM"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"J.S.B. Mitchell, G. Rote and G. W\u00f6ginger. Computing the Minimum Link Path Among a Set of Obstacles in the Plane. To appear in Proc. 6th ACM Symp. on Computational Geometry, 1990.","DOI":"10.1145\/98524.98537"},{"key":"19_CR15","unstructured":"J.S.B. Mitchell. An Optimal Algorithm for Shortest Rectilinear Paths Among Obstacles in the Plane. In Abstracts of the First Canadian Conference on Computational Geometry, page 22, 1989."},{"key":"19_CR16","volume-title":"Computational Geometry","author":"M.I. Shamos","year":"1978","unstructured":"M.I. Shamos. Computational Geometry. PhD thesis, Yale University, New Haven, CN, 1978."},{"issue":"1","key":"19_CR17","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0215014","volume":"15","author":"M. Sharir","year":"1986","unstructured":"M. Sharir, A. Schorr. On Shortest Paths in Polyhedral Spaces. SIAM Journal of Computing, 15(1):193\u2013215, 1986.","journal-title":"SIAM Journal of Computing"},{"key":"19_CR18","unstructured":"S. Suri. Minimum Link Paths in Polygons and Related Problems. Ph. D. thesis, Johns Hopkins University, 1986."},{"key":"19_CR19","doi-asserted-by":"crossref","first-page":"46","DOI":"10.5957\/jsr.1974.18.1.46","volume":"18","author":"G.E. Wangdahl","year":"1974","unstructured":"G.E. Wangdahl, S.M. Pollack, J.B. Woodward. Minimum-Trajectory Pipe Routing. Journal of Ship Research, 18:46\u201349, 1974.","journal-title":"Journal of Ship Research"}],"container-title":["Lecture Notes in Computer Science","SWAT 90"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52846-6_91.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T03:16:43Z","timestamp":1640920603000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52846-6_91"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540528463","9783540471646"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-52846-6_91","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}