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).

• 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²).