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(n3/2).
- 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 + k2).
(SODA paper)
Co-authors –
Publications –
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
UC Irvine
Semi-automatically filtered
from a common source file.