## 6 February 1998:

Shortest paths in an arrangement with k line orientations

David Hart, ICS, UC Irvine

Suppose one has a line arrangement in which many lines are
parallel, so that the number of different line orientations is k,
and one wants to find a shortest path from one point on a line in
the arrangement to another such point. Using known techniques one
can find the shortest path in time and space O(n^{2}). We
present an algorithm that can find the shortest path in
O(n+k^{2}) time and space.