{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:10:38Z","timestamp":1737090638031,"version":"3.33.0"},"reference-count":7,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5215,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1992,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Finding short paths through mazes of rectangles has applications in VLSI wire\u2010routing and robotics. This paper introduces and analyzes heuristic algorithms for finding short paths, under the assumption that the algorithms have no information about rectangles not already encountered along a path. Tight worst\u2010case bounds are derived for the ratio of the length of these algorithms' paths to the lengths of shortest paths. A model of random mazes is defined for testing the typical or average\u2010case behavior of algorithms. Although specially designed mazes can force the heuristic algorithms to give long paths, simulations and analysis show that the better heuristics usually give paths nearly as short as possible.<\/jats:p>","DOI":"10.1002\/net.3230220404","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T12:21:44Z","timestamp":1178972504000},"page":"349-367","source":"Crossref","is-referenced-by-count":3,"title":["Paths through a maze of rectangles"],"prefix":"10.1002","volume":"22","author":[{"suffix":"Jr.","given":"E. G.","family":"Coffman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E. N.","family":"Gilbert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","first-page":"494","volume-title":"Navigating in unfamiliar geometric terrain","author":"Blum A.","year":"1991"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"K. L.Clarkson S.Kapoor andP. M.Vaidya. Rectilinear shortest paths through polygonal obstacles inO(n(log n)2) time.Proceedings of the 3rd Annual Conference on Computational Geometry(1987)251\u2013257.","DOI":"10.1145\/41958.41985"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110307"},{"key":"e_1_2_1_5_2","unstructured":"J. S. B.Mitchell Shortest rectilinear paths among obstacles.Computational and Geometric Aspects of Robotics. Proceedings of the 1st International Conference on Industrial and Applied Math (ICIAM'87) Paris (1987)39\u201384."},{"key":"e_1_2_1_6_2","first-page":"610","volume-title":"Shortest paths without a map","author":"Papadimitriou C.","year":"1989"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187714"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676904"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230220404","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230220404","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:52:34Z","timestamp":1737006754000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230220404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,7]]},"references-count":7,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1992,7]]}},"alternative-id":["10.1002\/net.3230220404"],"URL":"https:\/\/doi.org\/10.1002\/net.3230220404","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"type":"print","value":"0028-3045"},{"type":"electronic","value":"1097-0037"}],"subject":[],"published":{"date-parts":[[1992,7]]}}}