{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T13:14:25Z","timestamp":1726146865220},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1991,6]]},"abstract":"<jats:p> We consider a rectilinear shortest path problem among weighted obstacles. Instead of restricting a path to totally avoid obstacles we allow a path to pass through them at extra costs. The extra costs are represented by the weights of the obstacles. We aim to find a shortest rectilinear path between two distinguished points among a set of weighted obstacles. The unweighted case is a special case of this problem when the weight of each obstacle is +\u221e. By using a graph-theoretical approach, we obtain two algorithms which run in O(n log <jats:sup>2<\/jats:sup> n) time and O(n log n) space and in O(n log <jats:sup>3\/2<\/jats:sup> n) time and space, respectively, where n is the number of the vertices of the obstacles. <\/jats:p>","DOI":"10.1142\/s0218195991000104","type":"journal-article","created":{"date-parts":[[2004,11,27]],"date-time":"2004-11-27T01:43:01Z","timestamp":1101519781000},"page":"109-124","source":"Crossref","is-referenced-by-count":24,"title":["SHORTEST RECTILINEAR PATHS AMONG WEIGHTED OBSTACLE"],"prefix":"10.1142","volume":"01","author":[{"given":"D. T.","family":"LEE","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering  and Computer Science, Northwestern University, Evanston,  IL 60208, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. D.","family":"YANG","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering  and Computer Science, Northwestern University, Evanston,  IL 60208, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T. H.","family":"CHEN","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering  and Computer Science, Northwestern University, Evanston,  IL 60208, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,1,25]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195991000104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:33:38Z","timestamp":1565130818000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195991000104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,1,25]]},"published-print":{"date-parts":[[1991,6]]}},"alternative-id":["10.1142\/S0218195991000104"],"URL":"https:\/\/doi.org\/10.1142\/s0218195991000104","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}