{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T03:19:30Z","timestamp":1774495170436,"version":"3.50.1"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2001,12]]},"abstract":"<jats:p> In this paper, we study several geometric path query problems. Given a scene of disjoint polygonal obstacles with totally n vertices in the plane, we construct efficient data structures that enable fast reporting of an \"optimal\" obstacle-avoiding path (or its length, cost, directions, etc) between two arbitrary query points s and t that are given in an on-line fashion. We consider geometric paths under several optimality criteria: L <jats:sub>m<\/jats:sub> length, number of edges (called links), monotonicity with respect to a certain direction, and some combinations of length and links. Our methods are centered around the notion of gateways, a small number of easily identified points in the plane that control the paths we seek. We give efficient solutions for several special cases based upon new geometric observations. We also present solutions for the general cases based upon the computation of the minimum size visibility polygon for query points. <\/jats:p>","DOI":"10.1142\/s0218195901000675","type":"journal-article","created":{"date-parts":[[2003,5,7]],"date-time":"2003-05-07T08:18:55Z","timestamp":1052295535000},"page":"617-645","source":"Crossref","is-referenced-by-count":11,"title":["ON GEOMETRIC PATH QUERY PROBLEMS"],"prefix":"10.1142","volume":"11","author":[{"given":"DANNY Z.","family":"CHEN","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA"}]},{"given":"OVIDIU","family":"DAESCU","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Ricardson, TX 75083, USA"}]},{"given":"KEVIN S.","family":"KLENK","sequence":"additional","affiliation":[{"name":"Ford Motor Company, Dearborn, MI 48101, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000234"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(91)90002-V"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90004-P"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00020-8"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796307194"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.2307\/1941844"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"issue":"1","key":"p_20","first-page":"3","volume":"4","author":"ElGindy H.","year":"1994","journal-title":"International cations"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90064-O"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(96)80467-7"},{"key":"p_37","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"p_39","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758836"},{"key":"p_41","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758855"},{"issue":"2","key":"p_47","first-page":"205225","volume":"6","author":"Schuierer S.","year":"1996","journal-title":"Internatational Journal of Computational Geometry & Applications"},{"key":"p_49","doi-asserted-by":"publisher","DOI":"10.1007\/BF02067242"},{"issue":"3","key":"p_53","first-page":"457","volume":"24","year":"1995","journal-title":"Comput"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195901000675","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:28:00Z","timestamp":1565137680000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195901000675"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,12]]},"references-count":18,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2001,12]]}},"alternative-id":["10.1142\/S0218195901000675"],"URL":"https:\/\/doi.org\/10.1142\/s0218195901000675","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,12]]}}}