Shortest paths in an arrangement with k line orientations
David Eppstein, David W. Hart · 1999
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 time and space O(n + k 2 ). 1 Introduction Given a line arrangement and two points located on lines of the arrangement, it is natural to ask how to compute a shortest path from one point to the other, traveling only on lines of the arrangement. Of course, one can simply construct the arrangement, interpret its vertices and edges as forming a planar graph, and find a shortest path in this graph. It is well known how to compute arrangements in time O(n 2 ), and the resulting planar graph has O(n 2 ) vertices and edges. Klein et al. [4] show how to compute shortest paths in planar graphs in linear time, hence the sh...