Abstract. Given a set of nonintersecting polygonal obstacles in the plane, the link distance between two points s and t is the minimum number of edges required to form a polygonal path connecting s to t that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in time O(Ect(n) log 2 n) (and space O(E)), where n is the total number of edges of the obstacles, E is the size of the visibility graph, and c~(n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted at s) of minimum-link paths from s to all obstacle vertices. This leads to a method of solving the query version of our problem (for query points t).
To find a minimum-link s-t path between two points s and t in an arbitrary polygonal domain P, Mitchell REF gave an O(Eα(n) log 2 n) time algorithm, where α(n) is the inverse of Ackermann's function and E is the size of the visibility graph of P and E = Θ(n 2 ) in the worst case.
Minimum-link paths among obstacles in the plane
Algorithmica
Algorithmica
Mathematics Computer Science