### Technical Report No. 39, October 1991 - Abstract

**Gabriele Reich:**

*Finitely-Oriented Shortest Paths in the Presence of Polygonal Obstacles*

Given a set of non-intersecting simple polygons, a set of points in
the plane, and a set of fixed orientations, we compute a graph such
that for any two input points there exists a shortest path in *G*
whose
length equals the length of a shortest path between these points in
the
plane that does not intersect any polygon and that consists only of
line segments of the given orientations.
This graph may serve as a basis not only to compute shortest paths
but
also for various other network applications, like e.g. minimum
spanning
trees or Steiner minimal trees.
We show that for *f* fixed orientations and *n* input points the
size
of the graph *G* is *O(f*n*log n)* and that *G* can be
computed
in time *O(f*n*log n)*.

report39.ps.gz