Computing Shortest Paths amid Convex Pseudodisks
Danny Z. Chen, John E. Hershberger, Haitao Wang · SIAM Journal on Computing · 2013
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)$.