Minimum-link paths among obstacles in the plane
Joseph S. B. Mitchell, Günter Rote, Gerhard J. Woeginger · 1990
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 Ο(Eα(n) log2 n) (and space Ο(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.