ICS Theory Group

ICS 269, Fall 2000: Theory Seminar

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.