The rectilinear shortest path problem can be stated as - given a set of m non-intersecting simple polygonal obstacles in the plane, find a shortest rectilinear (L1) path from a point s to a point t which avoids all the obstacles. The path can touch an obstacle but does not cross it. This paper presents an algorithm with time complexity O(n + m(lg n)3/2), which is close to the known lower bound of Ω(n + m lg m) for finding such a path. Here, n is the number of vertices of all the obstacles together. Our algorithm is of O(n +m(lg m)3/2) space complexity.
['Rajasekhar Inkulu', 'Sanjiv Kapoor']
Finding a rectilinear shortest path in R 2 using corridor based staircase structures