Joseph S. B. Mitchell, Günter Rote, and Gerhard
Woeginger:
Minimum-link paths among obstacles in the plane
- Algorithmica 8 (1992), 431–459, (Zbl
788.68144).
doi:10.1007/BF01758855
- 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.)
Abstract
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).
Last update: August 16, 2004.