## Oct 27 2000:

Approximating the Shortest Path in a Line Arrangement

Speaker: David Hart, ICS, UC Irvine

No one knows how to compute the shortest path between two points in
a line arrangement in less than \theta(n^2). We first show that one
can simplify this to finding a shortest path in a grid of quadrilaterals
(which has the complication of having paths traveling on a boundary
around the grid).

The only previously published approximation algorithm gives a factor
of 2 approximation to the shortest path in O(n log n). We use the
simpler grid structure to give a much better approximation algorithm.

This is a preliminary version of what will be a job talk. The
associated paper is to be submitted for publication.