Computing shortest paths amid pseudodisks
Danny Z. Chen, Haitao Wang · Symposium on Discrete Algorithms · 2011
Multiple objects in the plane are called pseudodisks if they are convex and the boundaries of any two of them intersect transversely at most twice. Given a set of n (possibly intersecting) pseudodisks of O(1) complexity each and two points s and t in the plane, we develop an O(n2) time algorithm for computing a shortest s-to-t path avoiding the pseudodisks. In over two decades, the previously best algorithms for this problem take O(n2 log n) time, even when all 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. Our algorithm actually solves a more general version of the motion planning problem. Further, as a by-product of our approach, we present an O(n2) time algorithm for computing the visibility graph of a set of n (possibly intersecting) pseudodisks in the plane. The previously best known time bound of this visibility problem is O(n2 log n). In addition, for n pairwise disjoint (non-polygonal) convex objects of O(1) complexity each in the plane, we compute a shortest s-to-t path avoiding all objects in O(n log n + k) time, where k is the size of the visibility graph of the objects.