# ICS 269, Winter 1997: Theory Seminar

## 28 Feb 1997:

An Efficient Algorithm for Shortest Paths in Vertical and
Horizontal Segments

David Hart, ICS, UC Irvine

Suppose one has a line segment arrangement consisting entirely
of vertical and horizontal segments, and one wants to find the
shortest path from one point to another along these segments. Using
known algorithms one can solve this in O(*n*^{2}) time
and in O(*n*^{2}) space. We show that it is possible
to find a shortest path in time
O(*n*^{1.5} log *n*) and space
O(*n*^{1.5}). Furthermore, if only one path endpoint
is known in advance, it is possible to preprocess the arrangement
in the same time and space and then find shortest paths for query
points in time O(log *n*).