{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T06:24:50Z","timestamp":1764570290621},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1994,3]]},"abstract":"<jats:p> Given a set \u212c of n barriers, the shortest route query SRQ problem asks for a preprocessing of \u212c such that a description of the shortest route between two points (origin and destination) can be reported efficiently. In this manuscript we present efficient sequential and parallel algorithms for the SRQ problem where the barriers in \u212c are disjoint planar rectangles whose sides are parallel to the coordinate axes, and subsequent queries ask for the shortest L<jats:sub>1<\/jats:sub> route between two arbitrary points which avoids the barriers in \u212c. The segments forming such route are also restricted to be parallel to the coordinate axes. <\/jats:p><jats:p> For this problem we we present sequential and parallel preprocessing algorithms which allow for reporting the shortest distance between two arbitrary query points in O( log n) time with a single processor. The route itself can also be constructed in time proportional to its number of segments. Our method is based on constructing three planar graphs, called carrier graphs, that contain the shortest route information in a succinct form. Each graph can then be searched using graph theoretic techniques. Using the same techniques we also present a parallel algorithm for computing the orthogonal shortest distance between two points among rectangular obstacles which runs in poly-logarithmic time using sub-quadratic number of processors on the CREW PRAM model of computation. <\/jats:p>","DOI":"10.1142\/s0218195994000021","type":"journal-article","created":{"date-parts":[[2004,11,19]],"date-time":"2004-11-19T02:21:13Z","timestamp":1100830873000},"page":"3-24","source":"Crossref","is-referenced-by-count":16,"title":["ORTHOGONAL SHORTEST ROUTE QUERIES AMONG AXES PARALLEL RECTANGULAR OBSTACLES"],"prefix":"10.1142","volume":"04","author":[{"given":"HOSSAM","family":"ELGINDY","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Newcastle, University Drive, Callaghan, New South Wales 2308, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PINAKI","family":"MITRA","sequence":"additional","affiliation":[{"name":"School of Computing Science, Simon Fraser Univerity, Burnaby, BC V5A 1S6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195994000021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:30:56Z","timestamp":1565137856000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195994000021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1994,3]]}},"alternative-id":["10.1142\/S0218195994000021"],"URL":"https:\/\/doi.org\/10.1142\/s0218195994000021","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]}}}