{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T16:36:18Z","timestamp":1768408578993,"version":"3.49.0"},"reference-count":14,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,3,9]],"date-time":"2007-03-09T00:00:00Z","timestamp":1173398400000},"content-version":"vor","delay-in-days":8590,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1983,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:italic>S<\/jats:italic> be a set of <jats:italic>n<\/jats:italic> horizontal and vertical segments on the plane, and let <jats:italic>s, t<\/jats:italic> \u2208 <jats:italic>S.<\/jats:italic> A Manhattan path (of length <jats:italic>k<\/jats:italic>) from <jats:italic>s<\/jats:italic> to <jats:italic>t<\/jats:italic> is an alternating sequence of horizontal and vertical segments <jats:italic>s<\/jats:italic> = <jats:italic>r<\/jats:italic><jats:sub>0<\/jats:sub>, <jats:italic>r<\/jats:italic><jats:sub>1<\/jats:sub>,\u2026,<jats:italic>r<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub> = <jats:italic>t<\/jats:italic> where <jats:italic>r<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub> intersects <jats:italic>r<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic>+1<\/jats:sub>, 0 \u2264 <jats:italic>i<\/jats:italic> &lt; <jats:italic>k.<\/jats:italic> An from all <jats:italic>s<\/jats:italic> \u2208 <jats:italic>S<\/jats:italic> to <jats:italic>t.<\/jats:italic> Also given is a method to determine a maximum set of crossings (intersections of segments) with no two on the same segment, as well as a maximum set of nonintersecting segments, both in <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>3\/2<\/jats:sup> log<jats:sup>2<\/jats:sup> log<jats:sup>2<\/jats:sup> <jats:italic>n<\/jats:italic>) time. The latter algorithm is applied to decomposing, in <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>3\/2<\/jats:sup> log<jats:sup>2<\/jats:sup> <jats:italic>n<\/jats:italic>) time, a hole\u2010free union of <jats:italic>n<\/jats:italic> rectangles with sides parallel to the coordinate axes into the minimal number of disjoint rectangles. All the algorithms require <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>) space, and for all of them the factor log<jats:sup>2<\/jats:sup> <jats:italic>n<\/jats:italic> can be improved to log <jats:italic>n<\/jats:italic> log log <jats:italic>n<\/jats:italic>, at the cost of some complication of the basic data structure used.<\/jats:p>","DOI":"10.1002\/net.3230130308","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T16:50:01Z","timestamp":1178902201000},"page":"399-409","source":"Crossref","is-referenced-by-count":36,"title":["Finding a manhattan path and related problems"],"prefix":"10.1002","volume":"13","author":[{"suffix":"Jr.","given":"Witold","family":"Lipski","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,3,9]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974"},{"key":"e_1_2_1_3_2","unstructured":"J. L.Bentley Solutions to Klee's rectangle problems. Unpublished notes (1977)."},{"key":"e_1_2_1_4_2","unstructured":"J. L.BentleyandD.Wood An optimal worst\u2010case algorithm for reporting intersections of rectangles. Unpublished (1979)."},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"P.van Emde Boas Preserving order in a forest in less than logarithmic time.Proc. 16th Annual Symp. on Foundations of Comp. Sci. Berkeley 1975 pp.75\u201384.","DOI":"10.1109\/SFCS.1975.26"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90068-0"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_9_2","volume-title":"Fundamentals of Computer Algorithms","author":"Horowitz E.","year":"1978"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90023-7"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90011-5"},{"key":"e_1_2_1_11_3","first-page":"105","volume":"2","year":"1981","journal-title":"Erratum"},{"key":"e_1_2_1_11_4","first-page":"301","volume":"3","year":"1982","journal-title":"Corrigendum"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90008-0"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","first-page":"245","DOI":"10.3233\/FI-1978-2116","article-title":"On two dimensional data organization II","volume":"2","author":"Lipski W.","year":"1979","journal-title":"Fund. Informaticae"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130308","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130308","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,19]],"date-time":"2023-10-19T22:54:45Z","timestamp":1697756085000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130308"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,9]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1983,9]]}},"alternative-id":["10.1002\/net.3230130308"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130308","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,9]]}}}