Given a line arrangement and points s and t on lines of the arrangement, the best known algorithm for finding a shortest path from s to t traveling on lines of the arrangement takes O(n^2) time. We present an algorithm that finds a 1+epsilon approximation of the path in O(nlogn + (n/epsilon^2) log(1/epsilon)) time.
We will also mention new progress in finding an exact shortest path.
This is a practice talk for... TBA. It is substantially changed (and hopefully "new and improved") from a previous talk on this topic.