|
Abstract : |
This paper appeared in Algorithmica 8 ?1992?, 431?459. 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?En ? 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 n ? denotes the extremely slowly growing inverse of Ackermann's function. We showhow 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?. 1, |
