Rectilinear shortest paths with rectangular barriers

Abstract

We address ourselves to an instance of the Shortest Path problem with obstacles where a shortest path in the Manhattan (or L1) distance is sought between two points (source and destination) and the obstacles are n disjoint rectangles with sides parallel to the coordinate axes. A plane sweep technique is applied rather than the graph theoretic approach frequently used in the literature. We show that there has to be a path of minimum length between the two given points which is monotone in at least one of x or y directions. Then we present an algorithm of time complexity Ο(n log n) for constructing that path and show that our algorithm is optimal.