Joseph S. B. Mitchell, Günter Rote, and Gerhard Woeginger:

Minimum-link paths among obstacles in the plane

  1. Algorithmica 8 (1992), 431–459, (Zbl 788.68144). doi:10.1007/BF01758855
  2. Extended Abstract in: Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, California, June 6–8, 1990. Association for Computing Machinery, 1990; pp. 63–72. doi:10.1145/98524.98537 (This is a preliminary and shortened version of 1.)


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(Eα(n)log2n) 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 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).
  PostScript file (gzipped)   pdf file   free PDF view@Springer
other papers about this subject
Last update: August 16, 2004.