{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T06:15:56Z","timestamp":1792649756775,"version":"4.5.0"},"reference-count":17,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":8075,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1984,9]]},"abstract":"Abstract<\/jats:title>\n \n In this paper we address the problem of constructing a Euclidean shortest path between two specified points (source, destination) in the plane, which avoids a given set of barriers. This problem had been solved earlier for polygonal obstacles with the aid of the visibility graph. This approach however, has an \u03a9(n\n 2<\/jats:sup>\n ) time lower bound, if n is the total number of vertices of the obstacles. Our goal is to find interesting cases for which the solution can be obtained without the explicit construction of the entire visibility graph. The two cases are (i) the path must lie within an n\u2010vertex simple polygon; (ii) the obstacles are n disjoint and parallel line segments. In both instances greedy O(n log n) time algorithms can be developed which solve the problems by constructing the shortest\u2010path tree from the source to all the vertices of the obstacles and to the destination.\n <\/jats:p>","DOI":"10.1002\/net.3230140304","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T14:16:50Z","timestamp":1178893010000},"page":"393-410","source":"Crossref","is-referenced-by-count":277,"title":["Euclidean shortest paths in the presence of rectilinear barriers"],"prefix":"10.1002","volume":"14","author":[{"given":"D. T.","family":"Lee","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F. P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Analysis and Design of Computer Algorithms","author":"Aho A. V.","year":"1974"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130307"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_5_2","unstructured":"S.Even Graph Algorithms. Computer Science Potomac MD (1979)."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90062-5"},{"key":"e_1_2_1_7_2","unstructured":"D. G.Kirkpatrick Optimal search in planar subdivisions. Manuscript Department of Computer Science University of British Columbia (1979)."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110307"},{"key":"e_1_2_1_9_2","unstructured":"D. T.Lee Proximity and reachability in the plane. Ph.D. thesis Technical Report ACT\u201012 Coordinated Science Laboratory University of Illinois at Urbana\u2010Champaign (1978)."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/358656.358681"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210035"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"J.Reif Complexity of the mover's problem and generalizations. InProceedings 20th IEEE Symposium on the Foundations of Computer Science San Juan 1979. IEEE New York (1980) pp.421\u2013427.","DOI":"10.1109\/SFCS.1979.10"},{"key":"e_1_2_1_14_2","unstructured":"J. T.SchwartzandM.Sharir On the piano mover's problem. Technical Report No. 41 Department of Computer Science Courant Institute of Mathematical Sciences New York University (1982)."},{"key":"e_1_2_1_15_2","unstructured":"M. I.Shamos Problems in computational geometry. Technical Report Department of Computer Science Carnegie\u2010Mellon University (1977)."},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"P. M.SpiraandA.Pan On finding and updating shortest paths and spanning trees.Proceedings IEEE 14th Annual Symposium on Switching and Automata Theory.IEEE New York (1973) pp.82\u201384.","DOI":"10.1109\/SWAT.1973.17"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"M.Tompa An optimal solution to a wire\u2010routing problem. InProceedings 12th ACM Symposium on Theory of Computing Los Angeles 1980. American Chemical Society Washington DC (1980) pp.161\u2013176.","DOI":"10.1145\/800141.804664"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","first-page":"46","DOI":"10.5957\/jsr.1974.18.1.46","article-title":"Minimum\u2010trajector pipe routing","volume":"18","author":"Wangdahl G. E.","year":"1974","journal-title":"J. Ship Res."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230140304","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230140304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,19]],"date-time":"2023-10-19T16:56:58Z","timestamp":1697734618000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230140304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,9]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1984,9]]}},"alternative-id":["10.1002\/net.3230140304"],"URL":"https:\/\/doi.org\/10.1002\/net.3230140304","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1984,9]]}}}