Approximating the shortest path in line arrangements.
David K. Hart · 2001
Suppose one has a line arrangement and one wants to find a shortest path from one point lying on a line of the arrangement to another such point. The best known time bound for computing this is O(n 2 ). We develop an algorithm that finds a 1 + ffl approximation of the shortest path in time O(n log n + (minfn; 1 ffl 2 g) 1 ffl log 1 ffl ). 1