minimum-link paths among obstacles in the plane
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 &Ogr; ( E&agr; ( n ) log 2 n ) (and space &Ogr; ( E )), where n is the total number of edges of the obstacles, E is the size of the visibility graph, and &agr; ( n ) denotes the extremely slowly growing inverse of Ackermann's function.
linking distance point algorithm timing space size visibility graph functional