{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,29]],"date-time":"2026-08-29T19:02:52Z","timestamp":1788030172035,"version":"build-2784847793"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>Multiple objects in the plane are called pseudodisks if the boundaries of any two of them intersect transversely at most twice. Given a set of $n$ (possibly intersecting) convex pseudodisks of $O(1)$ complexity each and two points $s$ and $t$ in the plane, we present an efficient algorithm for computing a shortest $s$-to-$t$ path avoiding the pseudodisks. After the union of the pseudodisks is computed, which can be done in $O(n\\log n)$ randomized time or $O(n\\log^2 n)$ deterministic time, our algorithm runs in $O(n\\log n+k)$ deterministic time, where $k$ is the size of the extended visibility graph of the union of the pseudodisks. Note that $k = O(n^2)$ in the worst case. In over two decades, the previously best algorithms for this problem have not improved on the bound of $O(n^2\\log n)$ time, even when all the pseudodisks are pairwise disjoint disks. Our technique is also applicable to a motion planning problem of finding a shortest path to translate a convex object in the plane from one location to another avoiding a given set of polygonal obstacles, improving the previously best known solution and settling an open problem posed in 1988. Our algorithm actually solves a more general version of the open problem. Further, as a byproduct of our approach, we present an $O(n\\log n + k)$-time algorithm for computing the extended visibility graph of a set of $n$ (possibly intersecting) convex pseudodisks in the plane. The previously best known time bound for this visibility problem is $O(n^2 \\log n)$.<\/jats:p>","DOI":"10.1137\/110840030","type":"journal-article","created":{"date-parts":[[2013,6,19]],"date-time":"2013-06-19T10:13:31Z","timestamp":1371636811000},"page":"1158-1184","source":"Crossref","is-referenced-by-count":8,"title":["Computing Shortest Paths amid Convex Pseudodisks"],"prefix":"10.1137","volume":"42","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Hershberger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,6,19]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840436"},{"key":"atypb2","first-page":"116","author":"Chang E.","year":"2005","journal-title":"New York"},{"key":"atypb3","unstructured":"D.Z. Chen and H. Wang,\n                      Computing Shortest Paths Among Curved Obstacles in the Plane\n                      , preprint, arXiv:1103.3911, 2011."},{"key":"atypb4","first-page":"214","author":"Chew L.P.","year":"1985","journal-title":"New York"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570705"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840357"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/0220055"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90003-X"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/0214006"},{"key":"atypb11","first-page":"172","author":"Kapoor S.","year":"1988","journal-title":"New York"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187683"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530888"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000216"},{"key":"atypb15","first-page":"164","author":"Overmars M.H.","year":"1988","journal-title":"New York"},{"key":"atypb16","first-page":"248","author":"Pocchiola M.","year":"1995","journal-title":"New York"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90045-1"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/0215014"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/185675.185795"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90044-4"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110840030","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:31:07Z","timestamp":1787337067000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110840030"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110840030"],"URL":"https:\/\/doi.org\/10.1137\/110840030","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}