# David Eppstein - Publications

##
Publications with David Hart

**An efficient algorithm for shortest paths in vertical and horizontal
segments**.

D. Eppstein and
D. Hart.

*5th Worksh. Algorithms and Data Structures,* Halifax, Nova Scotia, 1997.

Springer, *Lecture Notes in
Comp. Sci.* 1272, 1997, pp. 234–247.
We show how to find shortest paths along the segments of
an arrangement of *n* vertical and horizontal line segments in the
plane, in time O(*n*^{3/2}).

(BibTeX –
Citations –
CiteSeer –
ACM DL)

**Shortest paths in an arrangement with ***k* line orientations.

D. Eppstein and
D. Hart.

*10th ACM-SIAM Symp. Discrete Algorithms,* Baltimore, 1999, pp. 310–316.
We show how to find shortest paths between two points on the lines of
an arrangement of *n* lines with *k* distinct orientations,
in time O(*n* + *k*^{2}).

(BibTeX –
SODA paper –
Citations –
CiteSeer)

Co-authors –
Publications –
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
UC Irvine

Semi-automatically filtered
from a common source file.