ICS Theory Group

ICS 269, Spring 2001: Theory Seminar

8 June 2001:
Approximating the Shortest Path in a Line Arrangement
David Hart

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.