{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:12:46Z","timestamp":1760440366642},"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> We consider paths composed of a minimum number of line segments parallel to a fixed set of c orientations that avoid a set of obstacles in the plane. We preprocess n line segment obstacles with disjoint interiors and a starting point A into a data structure using O(cn) space. With this data structure, we can determine the minimum number of line segments l of a path from A to a query point B in O(c log n) time and construct a path in additional O(l) time. Preprocessing takes O(c<jats:sup>2<\/jats:sup>n log n) time and space or O(c<jats:sup>2<\/jats:sup>n log <jats:sup>2<\/jats:sup> n) time and O(c<jats:sup>2<\/jats:sup>n) space. Usually c is a constant \u2014 as an example, c = 2 for rectilinear paths. <\/jats:p>","DOI":"10.1142\/s0218195994000045","type":"journal-article","created":{"date-parts":[[2004,11,19]],"date-time":"2004-11-19T02:21:13Z","timestamp":1100830873000},"page":"39-51","source":"Crossref","is-referenced-by-count":5,"title":["MINIMUM-LINK C-ORIENTED PATHS: SINGLE-SOURCE QUERIES"],"prefix":"10.1142","volume":"04","author":[{"given":"JOHN","family":"ADEGEEST","sequence":"first","affiliation":[{"name":"Dept. of Computer Science, Utrecht Univ., 3508 TB Utrecht, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARK","family":"OVERMARS","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, Utrecht Univ., 3508 TB Utrecht, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JACK","family":"SNOEYINK","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, UBC, Vancouver, B.C., Canada V6T 1Z2, 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\/S0218195994000045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:30:58Z","timestamp":1565137858000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195994000045"}},"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\/S0218195994000045"],"URL":"https:\/\/doi.org\/10.1142\/s0218195994000045","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]}}}