## 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`)log^{2}`n`)
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.