Joseph S. B. Mitchell, Günter Rote, and Gerhard
Minimum-link paths among obstacles in the plane
- Algorithmica 8 (1992), 431–459, (Zbl
- Extended Abstract in: Proceedings of the Sixth Annual
Berkeley, California, June 6–8, 1990. Association for Computing
1990; pp. 63–72.
(This is a preliminary and shortened version of 1.)
Given a set of nonintersecting polygonal obstacles in the plane, the
distance between two points s and t is the minimum
to form a polygonal path connecting s
to t that avoids all obstacles. We
present an algorithm that computes the link distance (and a
minimum-link path) between two points in time O(Eα(n)log2n)
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
Ackermann's function. We show how to extend our method to allow
of a tree (rooted at s) of minimum-link paths from s to all
vertices. This leads to a method of solving the query version of our
(for query points t).
Last update: August 16, 2004.