# 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.