Finding shortest paths in the plane in the presence of barriers to travel (for any \(l_ p\)-norm) (Q1058966)

This paper develops an efficient algorithm for the computation of the shortest paths between given sets of points (origins and destinations) in the plane, when these paths are constrained not to cross any of a finite set of polygonal (open or closed) barriers. It is proved that, when distances are measured by an \(l_ p\)-norm with \(1<p<\infty\), these paths are formed by sequences of connected straight line segments whose intermediate (e.g. apart from origin and destination) end points are barrier vertices. Moreover, only segments that locally support the barriers to which their end points belong are elligible for inclusion in a shortest path. The special case of one origin and one destination is considered, as well as the more general case of many origins and destinations. If n is the number of nodes (origins, destinations and barrier vertices), an algorithm is presented that builds that network of all shortest paths in \(O(n^ 2\log n)\) time. If the total number of edges in this network is e (bounded by \(n^ 2)\), the application of Dijkstra's algorithm enables this computation of the shortest paths from any origin to all destinations in O(e log n) time. If there are n origins, shortest paths from all destinations can thus be found in O(ne log n)\(\leq O(n^ 3\) log n) time. It is also shown that optimal solutions when distances are measured according to the rectilinear or max-norm (i.e. \(l_ p\)-norm with \(p=1\) or \(p=\infty)\) can be deduced from the results of the algorithm.