Approximating shortest paths in arrangements of lines
Prosenjit K. Bose, William Evans, David G. Kirkpatrick, Michael J. McAllister, Jack Scott Snoeyink · Canadian Conference on Computational Geometry · 1996
this paper, we study the problem of computing the shortest path between a pair of points on an arrangement of lines with respect to the Euclidean distance metric. Let L = f` 1 ; ` 2 ; : : : ; ` n g be a set of n lines and let A represent the arrangement induced by those lines. Given two points x; y on the arrangement, we want to find the shortest path between x and y such that each edge of the path lies on one of the lines in L.