On Shortest Paths in Line Arrangements
Kavitha Telikepalli, Michael J. McAllister · Max Planck Institute for Plasma Physics · 2003
In this paper, we show that the shortest path between two points in a grid-like arrangement of two pencils of lines has a particularly simple structure, as was previously conjectured. This gives a linear-time algorithm for computing shortest paths in such arrangements.