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).