ICS Theory Group

ICS 269, Winter 1998: Theory Seminar

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(n2). We present an algorithm that can find the shortest path in O(n+k2) time and space.