{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:10:41Z","timestamp":1760440241389},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1997,2]]},"abstract":"<jats:p> We present efficient algorithms for shortest-path and minimum-link-path queries between two convex polygons inside a simple polygon P, which acts as an obstacle to be avoided. Let n be the number of vertices of P, and h the total number of vertices of the query polygons. We show that shortest-path queries can be performed optimally in time O( log h + log n) (plus O(k) time for reporting the k edges of the path) using a data structure with O(n) space and preprocessing time, and that minimum-link-path queries can be performed in optimal time O( log h + log n) (plus O(k) to report the k links), with O(n<jats:sup>3<\/jats:sup>) space and preprocessing time. <\/jats:p><jats:p> We also extend our results to the dynamic case, and give a unified data structure that supports both queries for convex polygons in the same region of a connected planar subdivision [Formula: see text]. The update operations consist of insertions and deletions of edges and vertices. Let n be the current number of vertices in [Formula: see text]. The data structure uses O(n) space, supports updates in O( log <jats:sup>2<\/jats:sup> n) time, and performs shortest-path and minimum-link-path queries in times O( log h+ log <jats:sup>2<\/jats:sup>n) (plus O(k) to report the k edges of the path) and O( log h + k log <jats:sup>2<\/jats:sup> n), respectively. Performing shortest-path queries is a variation of the well-studied separation problem, which has not been efficiently solved before in the presence of obstacles. Also, it was not previously known how to perform minimum-link-path queries in a dynamic environment, even for two-point queries. <\/jats:p>","DOI":"10.1142\/s0218195997000077","type":"journal-article","created":{"date-parts":[[2003,10,16]],"date-time":"2003-10-16T10:47:26Z","timestamp":1066301246000},"page":"85-121","source":"Crossref","is-referenced-by-count":4,"title":["Optimal Shortest Path and Minimum-Link Path Queries between Two Convex Polygons inside a Simple Polygonal Obstacle"],"prefix":"10.1142","volume":"07","author":[{"given":"Yi-Jen","family":"Chiang","sequence":"first","affiliation":[{"name":"Department of Computer Science, Brown University Providence, R.I. 02912-1910, USA"}]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Brown University Providence, R.I.  02912-1910, USA"}]}],"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\/S0218195997000077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:31:02Z","timestamp":1565137862000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195997000077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,2]]},"references-count":0,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1997,2]]}},"alternative-id":["10.1142\/S0218195997000077"],"URL":"https:\/\/doi.org\/10.1142\/s0218195997000077","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,2]]}}}